TR18-012 Authors: Valentine Kabanets, Zhenjian Lu

Publication: 20th January 2018 05:19

Downloads: 582

Keywords:

We 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.