ECCC-Report TR05-043https://eccc.weizmann.ac.il/report/2005/043Comments and Revisions published for TR05-043en-usFri, 15 Apr 2005 19:08:15 +0300
Paper TR05-043
| Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2005/043We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same stretch but only fools circuits of depth $2$ with one arbitrary symmetric gate at the top. Our generator fools a strictly richer class of circuits than Nisan's generator for constant depth circuits (Combinatorica '91) (but Nisan's generator has a much bigger stretch).
In particular, we conclude that every function computable by uniform $\poly(n)$-size \emph{probabilistic} constant depth circuits with $O(\log n)$ arbitrary symmetric gates is in $\mathit{TIME}\rb{2^{n^{o(1)}} }$. This seems to be the richest probabilistic circuit class known to admit a subexponential derandomization.
Our generator is obtained by constructing an explicit function $f : \zo^n \to \zo$ that is very hard \emph{on average} for constant-depth circuits of size $n^{\eps \cdot \log n}$ with $\eps \log^2 n$ arbitrary symmetric gates, and plugging it into the Nisan-Wigderson pseudorandom generator construction (FOCS '88). The proof of the average-case hardness of this function is a modification of arguments by Razborov and Wigderson (IPL '93), and Hansen and Miltersen (MFCS '04), and combines H{\r{a}}stad's switching lemma (STOC '86) with a multiparty communication complexity lower bound by Babai, Nisan and Szegedy (STOC '89).
Fri, 15 Apr 2005 19:08:15 +0300https://eccc.weizmann.ac.il/report/2005/043