Improved pseudorandomness for unordered branching programs through local monotonicity
Improved pseudorandomness for unordered branching programs through local monotonicity
复制标题
通过局部单调性改进无序分支程序的伪随机性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Avishay Tal
中科院分区：
文献类型：
--
作者：
Eshan Chattopadhyay;Pooya Hatami;Omer Reingold;Avishay Tal
我们提出一个具有种子长度的显式假体生成器（（logn）W+1），用于读取，遗忘，宽度W分支程序，可以按任何顺序读取其输入位。 （焦点12）他们需要种子长度N1/2+O（1）。分支程序b：{0,1} n→{0,1}，任何k∈{1，…，n}，[不显示复杂公式]这设置了Reingold，Steinke和vadhan（Random'13）提出的猜想我们的分析在分支程序的边缘标签上彻底使用局部单调性。
We present an explicit pseudorandom generator with seed length Õ((logn)w+1) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impagliazzo, Meka and Zuckerman (FOCS’12) where they required seed length n1/2+o(1). A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width w read-once, oblivious branching program B:{0,1}n→ {0,1}, any k ∈ {1,…,n}, [complex formula not displayed] This settles a conjecture posed by Reingold, Steinke and Vadhan (RANDOM’13). Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.