Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs
复制标题
宽度 3 分支程序的伪随机性和傅立叶增长界
DOI：
10.4086/toc.2017.v013a012
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Andrew Wan
中科院分区：
文献类型：
--
作者：
T. Steinke;Salil P. Vadhan;Andrew Wan
我们提出了一个明确的伪和生成器，用于遗忘，读取，宽度3分支程序，可以按任何顺序读取其输入位。发电机的种子长度O〜（log^3 n）。
该模型的先前最著名的种子长度是n^{1/2+o（1）}，这是由于不受欢迎的，Meka和Zuckerman（focs'12）。我们的工作概括了Reingold，Steinke和Vadhan（Random'13）的最新结果，用于排列分支程序。我们的发电机的主要技术新颖性是宽度3的傅立叶生长，即遗忘的，一开始的分支程序。具体来说，我们表明，对于任何f：{0,1}^n-> {0,1}，由这样的分支程序计算出来，在[n]中计算的k，sum_ {| s | = k} | hat {f} （S）| <n^2 *（o（\ log n））^k，
其中f（x）= sum_s hat {f}（s）（-1）^是Z_2^ n的标准傅立叶变换。傅立叶生长的基本O（log n）紧密到log log n的因素。
We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ).
The previously best known seed length for this model is n^{1/2+o(1)} due to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM'13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f : {0,1}^n -> {0,1} computed by such a branching program, and k in [n], sum_{|s|=k} |hat{f}(s)| < n^2 * (O(\log n))^k,
where f(x) = sum_s hat{f}(s) (-1)^ is the standard Fourier transform over Z_2^n. The base O(log n) of the Fourier growth is tight up to a factor of log log n.