ECCC-Report TR18-012https://eccc.weizmann.ac.il/report/2018/012Comments and Revisions published for TR18-012en-usSat, 20 Jan 2018 05:19:07 +0200
Paper TR18-012
| Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates |
Valentine Kabanets,
Zhenjian Lu
https://eccc.weizmann.ac.il/report/2018/012We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed size
$$\exp\left(O(\sqrt{d\cdot\log n\cdot \log\log (n/\epsilon)})\right);$$ this can give a super-polynomial stretch even for a sub-exponentially small error parameter $\epsilon=\exp(-n^{\gamma})$, for any $\gamma=o(1)$. In contrast, the best known PRGs for PTFs of [Meka & Zuckerman, 2013; Kane, 2012] cannot achieve such a small error, although they do have a much shorter seed size for any constant error $\epsilon$.
For the case of circuits with degree-$d$ PTF gates on $n$ inputs, our PRG can fool circuits with at most $n^{\alpha/d}$ gates with error $\exp(-n^{\alpha/d})$ and seed length $n^{O(\sqrt{\alpha})}$, for any $\alpha>1$.
While a similar NW PRG construction was observed by Lovett and Srinivasan [Lovett & Srinivasan, 2011] to work for the case of constant-depth (AC$^0$) circuits with few PTF gates, the application of the NW generator to the case of general (unbounded depth) circuits consisting of a sublinear number of PTF gates does not seem to have been explicitly stated before. We do so in this note.Sat, 20 Jan 2018 05:19:07 +0200https://eccc.weizmann.ac.il/report/2018/012