# 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