Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-012 | 20th January 2018 05:16

Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates


Authors: Valentine Kabanets, Zhenjian Lu
Publication: 20th January 2018 05:19
Downloads: 128


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.

ISSN 1433-8092 | Imprint