ECCC-Report TR12-116https://eccc.weizmann.ac.il/report/2012/116Comments and Revisions published for TR12-116en-usFri, 14 Sep 2012 18:54:55 +0300
Revision 1
| A Derandomized Switching Lemma and an Improved Derandomization of AC0 |
Luca Trevisan,
TongKe Xue
https://eccc.weizmann.ac.il/report/2012/116#revision1We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$.
A seed length of $O(\log^{2d + \Omega(1)} M)$ is best possible given Nisan-type generators and the current state of circuit lower bounds; Seed length $\Omega(\log^d M/\epsilon)$ 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 $\tilde O(\log^2 M/\epsilon)$ 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.
Fri, 14 Sep 2012 18:54:55 +0300https://eccc.weizmann.ac.il/report/2012/116#revision1
Paper TR12-116
| A Derandomized Switching Lemma and an Improved Derandomization of AC0 |
Luca Trevisan
https://eccc.weizmann.ac.il/report/2012/116We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$.
A seed length of $O(\log^{2d + \Omega(1)} M)$ is best possible given Nisan-type generators and the current state of circuit lower bounds; Seed length $\Omega(\log^d M/\epsilon)$ 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 $\tilde O(\log^2 M/\epsilon)$ 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.
Thu, 13 Sep 2012 03:28:32 +0300https://eccc.weizmann.ac.il/report/2012/116