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

As discussed in a previous post, Razborov significantly simplified Bazzi’s proof, retaining the same quantitative bounds.

Bazzi had proved that, in order to show that a certain function (e.g. the function computed by a DNF) is -fooled by every -wise independent distribution, for a certain , it is sufficient (and, in fact, necessary) to show that there exist degree- real polynomials and such that

and

Bazzi also shows that constructing such functions reduces to finding one function which approximates in the norm and has “one-sided error,” meaning that if then we must have . Razborov shows that this good low-degree “one-sided approximation” for a given DNF can be easily constructed by modifying a result of Linial, Mansour and Nisan, who show that every DNF has good low-degree approximation in the norm.

In our proof, instead of working with -wise independent distributions we work with small-bias distributions, as defined by Naor and Naor. Recall that a distribution ranging over is -biased if for every subset we have

It is known how to construct pseudorandom generators of seed length whose output is -biased. It is also known that every -biased distribution is -close in statistical distance to a -wise independent distribution. From this, and from Bazzi’s result, it follows that if a distribution is -biased then it -fool every -variable, -term DNF. This means that every -biased distribution -fools every-term DNF, provided

and this gives an alternative way to construct a pseudorandom generator of seed length .

We show that, however, it is possible to do better if one works with small-bias distributions from the beginning.

Analogously to Bazzi’s characterization of functions fooled by -wise independent distributions, we have that, in order to show that every -biased distribution fools a given function , it is sufficient (and necessary) to find two functions and such that

and such that and have *small Fourier norm*. Recall that, in Bazzi’s characterization, the requirement on the approximating functions was to have small degree, that is to have their Fourier mass concentrated on coefficients defined over small sets. (Note that, for functions of bounded norm, having degree at most implies having Fourier norm , but a function can have small Fourier norm without having any low-degree approximation. This is analogous to the fact that an -biased distribution is close to being -wise independent if , but a distribution can be -wise independent without being a small-bias distribution.)

Following Bazzi-Razborov, for the special case of DNF this condition can be reduced to the problem of constructing a single function of small Fourier norm which provides a good one-sided approximation to a given DNF, which in turn can be reduced to the problem of just finding a function of small Fourier norm providing a good approximation to a given DNF. The latter problem is solved by Mansour with rather good parameters, allowing us to show that every -biased distribution -fools every -term -variable DNF, provided

which gives seed length .

Ultimately, one would like to achieve the optimal seed length . Unfortunately, there are limits to what can be achieved by reasoning about small-bias distributions.

Mansour showed that there exists an -term DNF and a -wise independent distribution , with such that does not -fool . For the case in which and are polynomially related, Mansour’s example shows that Bazzi’s proof is optimal: recall that Bazzi proves that every -wise independent distribution -fools every -term DNF provided .

In Mansour’s example, is the uniform distribution over assignments with an odd number of ones, which is definitely not a small-bias distribution. Unfortunately, a similar example can be constructed where is the uniform distribution over assignments to variables which have a number of ones which is not a multiple of 3. Such a distribution is -biased with , showing that our result too is nearly tight when and are polynomially related.

It remains a very interesting open question to show whether every -biased distribution -fools every -term DNF. This would give an -bit seed length generator that would foold DNFs and CNFs within a constant error. In particular, it would give a polynomial time deterministic algorithm that, given in input a CNF formula satisfied by at least a fraction of assignments would find a satisfying assignment.

As partial evidence of a positive answer to the above question, we show that every -biased distribution does -fool every *read-once* -term DNF.

Although “derandomizing” read-once DNFs is a trivial problem, it would be rather interesting to find pseudorandom generators of optimal seed length that -fool every read-once DNF. Unfortunately, we show that such generators cannot be based exclusively on small-bias distributions: we show that there is an -biased distribution with and an -term read-once DNF such that is not -fooled by . This is by far the most technical result in the paper, and maybe the type of counterexample that we construct could be useful elsewhere.

## 7 comments

Comments feed for this article

December 21, 2009 at 10:14 pm

lifeofpiThanks!

Do you believe using small-bias distributions improves the parameters of Braverman’s PRGs also?

December 22, 2009 at 1:09 pm

lucaIt should be possible to shave one or more log factors from the final seed length in the generator implied by Braverman’s analysis: if I am not mistaken, reasoning about L1 one gets slightly better bounds for Razborov-Smolemski too, not just for Linial-Nisan-Mansour. But the asymptotic would remain a seed of length to fool depth-d circuits, which is worse than Nisan’s generator, so we did not pursue this direction. It might be interesting to see if, for depth 3, one can do better than .

December 22, 2009 at 3:28 pm

lifeofpiThanks, I see. Do you have some intuition about why fooling linear polynomials is good for fooling DNF’s? One now naturally wonders about functions that fool higher degree polynomials…

December 22, 2009 at 9:03 pm

Anindya DeIf you want to approximate DNF by low degree polynomials, then a natural idea will be to show that DNFs can be approximated nicely by a low l1 norm combination of low degree polynomials (say degree 2 polynomials). However, I do not know of any analogue of fourier coefficients for degree 2 or higher polynomials.

December 23, 2009 at 8:01 am

lifeofpiAnindya, concretely, I meant using the sum of small-bias generators, as analysed by Viola in his “The sum of d small-bias generators fools polynomials of degree d”. But perhaps, I should read your paper first before making potentially unintelligent comments.

December 23, 2009 at 10:09 am

AnindyaIn fact, I also had the Bogdanov-Lovett-Viola (BLV) generator in mind but as I said, to use it, one has to prove that DNFs can be approximated well by a low L1 norm linear combination of degree d polynomials in the L2 sense. However, I do not know of any results in this direction. Also, to get logarithmic seed length, d < log log n because the seed length of the BLV generator goes as d.2^d.log(1/\epsilon) – (well, the exponential dependence on d may not be true/optimal but as Viola indicates, it will require a breakthrough to get a provable subexponential dependence on d)

December 23, 2009 at 12:51 pm

lucaI prefer to think of the question at the following level of abstraction:

Suppose we have proved that -wise independence fools a certain class of functions, e.g. DNFs, AC0 circuits, linear thresholds, etc.

Then we know by Alon-Goldreich-Mansour that -biased distributions also fool that class of functions. Can we do better? If we could use just, say, -biased distributions then we would reduce the seed length from to .

Suppose now that we know that every -biased distribution fools a certain class of functions, where is less than inverse-polynomial. Then a particular way to construct an -biased distribution is to sample independent -biased distributions and take their XOR. This uses the optimal $O(\log 1/\epsilon(n))$ seed length, but it is a potentially more powerful distribution (e.g. it is pseudorandom against polynomials of degree ). Could it suffice to XOR fewer copies of our basic -biased distribution and still derandomize the class of functions we are interested in?