Pseudorandomness for Read-Once, Constant-Depth Circuits
Pseudorandomness for Read-Once, Constant-Depth Circuits
复制标题
一次性读取、恒定深度电路的伪随机性
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Vadhan
中科院分区：
文献类型：
--
作者：
Sitan Chen;T. Steinke;S. Vadhan
对于在德摩根基上由一次读入、深度为\(D\)且扇入无界的电路所计算的布尔函数，我们给出了一个显式伪随机生成器，其种子长度约为\(O(\log^{D + 1}n)\)。此前对于该模型已知的最佳种子长度约为\(O(\log^{D + 4}n)\)，这是由特雷维桑和薛（CCC‘13）针对所有\(AC^0\)（不仅仅是一次读入的情况）所得到的。我们的工作利用了由莱因戈尔德、施泰因克和瓦德汉（RANDOM‘13）引入的用于伪随机性的傅里叶分析技术，以表明戈帕兰等人（FOCS‘12）的生成器能欺骗一次读入的\(AC^0\)。为此，我们证明了一次读入电路的一个新的傅里叶增长界，即对于每一个由一次读入、深度为\(D\)的电路所计算的\(F:\{0,1\}^n\rightarrow\{0,1\}\)，\(X\)（最后一个\(X\)不确定是否完整，如果还有后续内容，请提供完整信息以便更准确地翻译）
For Boolean functions computed by read-once, depth-D circuits with unbounded fan-in over the de Morgan basis, we present an explicit pseudorandom generator with seed length ~ O(log D+1 n). The previous best seed length known for this model was ~ O(log D+4 n), obtained by Trevisan and Xue (CCC ‘13 ) for all of AC 0 (not just read-once). Our work makes use of Fourier analytic techniques for pseudorandomness introduced by Reingold, Steinke, and Vadhan (RANDOM ‘13 ) to show that the generator of Gopalan et al. (FOCS ‘12 ) fools read-once AC 0 . To this end, we prove a new Fourier growth bound for read-once circuits, namely that for every F :f0; 1g n !f0; 1g computed by a read-once, depth-D circuit, X