A Derandomized Switching Lemma and an Improved Derandomization of AC0
A Derandomized Switching Lemma and an Improved Derandomization of AC0
复制标题
去随机化的切换引理和改进的 AC0 去随机化
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Tongke Xue
中科院分区：
文献类型：
--
作者：
L. Trevisan;Tongke Xue
我们描述了一个新的伪随机发生器AC 0。我们的生成器ε-fool深度为d，大小为M的电路，并使用长度为O（log<sup>d+4</sup> M/ε）的种子。之前最好的$d \geq 3$的构造是由Nisan提出的，其种子长度为O（log<sup>2d+6</sup> M/ε）。给定Nisan型生成器和电路的当前状态下界，种子长度O（log<sup>2d+Ω（1）</sup>M）是最佳可能的。种子长度Ω（log<sup>d</sup> M/ε）是给定当前电路状态下限的任何伪随机生成器构造的障碍。对于d=2，已知种子长度为0 μ m（log<sup>2</sup> M/ε）的伪随机发生器。我们的生成器是基于一个“伪随机限制”的生成器，它输出的限制，满足的结论的哈斯塔德切换引理，并使用一个种子的polylogarithmic长度。
We describe a new pseudorandom generator for AC0. Our generator ε-fools circuits of depth d and size M and uses a seed of length Ŏ(log<sup>d+4</sup> M/ε). The previous best construction for $d \geq 3$ was due to Nisan, and had seed length Ŏ(log<sup>2d+6</sup> M/ε). A seed length of O(log<sup>2d+Ω(1)</sup> M) is best possible given Nisan-type generators and the current state of circuit lower bounds. Seed length Ω(log<sup>d</sup> M/ε) is a barrier for any pseudorandom generator construction given the current state of circuit lower bounds. For d=2, a pseudorandom generator of seed length Ŏ(log<sup>2</sup> M/ε) was known. Our generator is based on a "pseudorandom restriction'' generator which outputs restrictions that satisfy the conclusions of the Hastad Switching Lemma and that uses a seed of polylogarithmic length.