Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits.
R. Servedio and L.-Y. Tan.
22nd International Workshop on Randomness and Computation (RANDOM), 2018, pp. 56:1--56:20.


Abstract:

We study correlation bounds and pseudorandom generators for depth-two circuits that consist of a $\SYM$-gate (computing an arbitrary symmetric function) or $\THR$-gate (computing an arbitrary linear threshold function) that is fed by $S$ $\AND$ gates. Such circuits were considered in early influential work on unconditional derandomization of Luby, Veli{\v{c}}kovi{\'c}, and Wigderson \cite{LVW93}, who gave the first non-trivial PRG with seed length $2^{O(\sqrt{\log(S/\eps)})}$ that $\eps$-fools these circuits.

In this work we obtain the first strict improvement of~\cite{LVW93}'s seed length: we construct a PRG that $\eps$-fools size-$S$ $\{\SYM,\THR\} \circ\mathsf{AND}$ circuits over $\zo^n$ with seed length \[ 2^{O(\sqrt{\log S })} + \polylog(1/\eps), \] an exponential (and near-optimal) improvement of the $\eps$-dependence of \cite{LVW93}. The above PRG is actually a special case of a more general PRG which we establish for constant-depth circuits containing multiple $\SYM$ or $\THR$ gates, including as a special case $\{\SYM,\THR\} \circ \acz$ circuits. These more general results strengthen previous results of Viola \cite{Vio06} and essentially strengthen more recent results of Lovett and Srinivasan \cite{LS11}.

Our improved PRGs follow from improved correlation bounds, which are transformed into PRGs via the Nisan--Wigderson ``hardness versus randomness'' paradigm \cite{NW94}. The key to our improved correlation bounds is the use of a recent powerful \emph{multi-switching} lemma due to H{\aa}stad \cite{Has14}.

Link to full version


Back to main papers page