Improved Pseudorandom Generators for Depth 2 Circuits
Improved Pseudorandom Generators for Depth 2 Circuits
复制标题
改进的深度 2 电路伪随机发生器
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Madhur Tulsiani
中科院分区：
文献类型：
--
作者：
Anindya De;Omid Etesami;Luca Trevisan;Madhur Tulsiani
我们证明了存在一个多项式(n,m)时间可计算的伪随机生成器，它能以1/多项式(n,m)的精度“欺骗”具有n个变量和m个项的析取范式（DNF），并且种子长度为O(log₂(nm) ⋅ log log(nm))。此前，针对深度为2的电路的最佳伪随机生成器的种子长度为O(log³(nm))，由巴齐（Bazzi）提出（2007年美国计算机协会计算机科学基础研讨会（FOCS））。
从我们的证明可以得出，一个偏差为1/m^{O(log(mn))}的分布能以1/多项式(nm)的精度“欺骗”具有m个项和n个变量的析取范式。对于逆多项式区分概率，这个结果几乎是紧的，因为我们表明对于任意的m和δ，存在一个偏差为1/m^{Ω(log(1/δ))}的分布X和一个具有m个项的析取范式φ，使得X不能以δ的精度“欺骗”φ。
对于一次读取析取范式（read-once DNF）的情况，我们表明种子长度O(log(mn) ⋅ log(1/δ))就足够了，这对于较大的δ是一种改进。
从我们的证明还可以得出，一个偏差为1/m^{O(log(1/δ))}的分布能以δ的精度“欺骗”所有具有m个项的一次读取析取范式。我们通过构造一个偏差为1/m^{Ω(log(1/δ))}的分布，它不能以δ的精度“欺骗”某个具有m个项的一次读取析取范式，表明这个结果也几乎是紧的。
We prove the existence of a poly(n,m)-time computable pseudorandom generator which "1/poly(n,m)-fools" DNFs with n variables and m terms, and has seed length O(log2nm ċ log log nm). Previously, the best pseudorandom generator for depth-2 circuits had seed length O(log3 nm), and was due to Bazzi (FOCS 2007).
It follows from our proof that a 1/mO(log mn)-biased distribution 1/poly(nm)-fools DNFs with m terms and n variables. For inverse polynomial distinguishing probability this is nearly tight because we show that for every m, δ there is a 1/mΩ(log 1/δ)-biased distribution X and a DNF φ with m terms such that φ is not δ-fooled by X.
For the case of read-once DNFs, we show that seed length O(log mn ċ log 1/δ) suffices, which is an improvement for large δ.
It also follows from our proof that a 1/mO(log 1/δ)-biased distribution δ-fools all read-once DNF with m terms. We show that this result too is nearly tight, by constructing a 1/mΩ(log 1/δ)-biased distribution that does not δ-fool a certain m-term read-once DNF.