ECCC-Report TR20-182https://eccc.weizmann.ac.il/report/2020/182Comments and Revisions published for TR20-182en-usSun, 09 May 2021 20:52:01 +0300
Revision 1
| An Improved Derandomization of the Switching Lemma |
Zander Kelley
https://eccc.weizmann.ac.il/report/2020/182#revision1We prove a new derandomization of Håstad's switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size $m$ using only $\widetilde{O}(\log m)$ random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing objects which are in some way provably-pseudorandom with respect to AC$^0$-circuits.
Here, we use our new derandomization to give an improved analysis of the pseudorandom generator of Trevisan and Xue for AC$^0$-circuits (CCC'13): we show that the generator $\varepsilon$-fools size-$m$, depth-$D$ circuits with $n$-bit inputs using only $\widetilde{O}(\log(m/\varepsilon)^{D} \cdot \log n)$ random bits. In particular, we obtain (modulo the $\log \log$-factors hidden in the $\widetilde{O}$-notation) a dependence on $m/\varepsilon$ which is best-possible with respect to currently-known AC$^0$-circuit lower bounds.Sun, 09 May 2021 20:52:01 +0300https://eccc.weizmann.ac.il/report/2020/182#revision1
Paper TR20-182
| An Improved Derandomization of the Switching Lemma |
Zander Kelley
https://eccc.weizmann.ac.il/report/2020/182We prove a new derandomization of Håstad's switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size $m$ using only $\widetilde{O}(\log m)$ random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing objects which are in some way provably-pseudorandom with respect to AC$^0$-circuits.
Here, we use our new derandomization to give an improved analysis of the pseudorandom generator of Trevisan and Xue for AC$^0$-circuits (CCC'13): we show that the generator $\varepsilon$-fools size-$m$, depth-$D$ circuits with $n$-bit inputs using only $\widetilde{O}(\log(m/\varepsilon)^{D} \cdot \log n)$ random bits. In particular, we obtain (modulo the $\log \log$-factors hidden in the $\widetilde{O}$-notation) a dependence on $m/\varepsilon$ which is best-possible with respect to currently-known AC$^0$-circuit lower bounds.Fri, 04 Dec 2020 22:39:05 +0200https://eccc.weizmann.ac.il/report/2020/182