Small-bias Distributions and DNFs

Two of my favorite challenges in unconditional derandomization are to find logarithmic-seed pseudorandom generators which are good against:

  1. log-space randomized algorithms
  2. {AC^0}, that is, constant depth circuits of polynomial size

Regarding the first challenge, the best known pseudorandom generator remains Nisan’s, from 1990, which requires a seed of {O(\log^2 n)} bits. Maddeningly, even if we look at width-3 oblivious branching programs, that is, non-uniform algorithms that use only {\log_2 3} bits of memory, nobody knows how to beat Nisan’s generator.

Regarding the second challenge, Nisan showed in 1988 that for every {d} there is a pseudorandom generator of seed length {O(\log^{2d+6} n)} against depth-{d} circuits of size {n}. The simplest case is that of depth-2 circuits, or, without loss of generality, of disjunctive-normal-form (DNF) formulas. When specialized to DNF formulas, Nisan’s generator has seed length {O(\log^{10} n)}, but better constructions are known in this case.

Luby, Velickovic and Wigderson improved the seed length to {O(\log^4 n)} in 1993. Bazzi’s celebrated proof of the depth-2 case of the Linian-Nisan conjecture implies that a {O(\log^2 m/\delta)}-wise independent distribution “{\delta}-fools” every {m}-term DNF, by which we mean that for every such DNF formula {\phi} and every such distribution {X} we have

\displaystyle  \left| \mathop{\mathbb P}_{x\sim X} [ \phi(x) = 1] - \mathop{\mathbb P}_{x\sim U} [\phi(x) = 1] \right| \leq \delta

where {U} is the uniform distribution over assignments. This leads to a pseudorandom generator that {\delta}-fools {n}-variable, {m}-term DNF formulas and whose seed length is {O(\log n \cdot \log^2 m/\delta)}, which is {O(\log^3 n)} when {m,n,\delta^{-1}} are polynomially related.

In a new paper with Anindya De, Omid Etesami, and Madhur Tulsiani, we show that an {n}-variable, {m}-term DNF can be {\delta}-fooled by a generator of seed length {O(\log n + \log^2 m/\delta \cdot \log\log m/\delta)}, which is {O(\log^{2+o(1)} n)} when {n,m,\delta^{-1}} are polynomially related.

Our approach is similar to the one in Razborov’s proof of Bazzi’s result, but we use small-bias distribution instead of {k}-wise independent distributions

Continue reading