Two of my favorite challenges in unconditional derandomization are to find logarithmic-seed pseudorandom generators which are good against:
- log-space randomized algorithms
- , 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 bits. Maddeningly, even if we look at width-3 oblivious branching programs, that is, non-uniform algorithms that use only bits of memory, nobody knows how to beat Nisan’s generator.
Regarding the second challenge, Nisan showed in 1988 that for every there is a pseudorandom generator of seed length against depth- circuits of size . 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 , but better constructions are known in this case.
Luby, Velickovic and Wigderson improved the seed length to in 1993. Bazzi’s celebrated proof of the depth-2 case of the Linian-Nisan conjecture implies that a -wise independent distribution “-fools” every -term DNF, by which we mean that for every such DNF formula and every such distribution we have
where is the uniform distribution over assignments. This leads to a pseudorandom generator that -fools -variable, -term DNF formulas and whose seed length is , which is when are polynomially related.
In a new paper with Anindya De, Omid Etesami, and Madhur Tulsiani, we show that an -variable, -term DNF can be -fooled by a generator of seed length , which is when 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 -wise independent distributions