The sandwich revolution: behind the paper

Louay Bazzi’s breakthrough paper “Polylogarithmic Independence Can Fool DNF Formulas” (2007) introduced the technique of sandwiching polynomials which is used in many subsequent works.  While some of these are about constant-depth circuits, for example those referenced in Bazzi’s text below, sandwiching polynomials have also been used to obtain results about sign polynomials, including for example a central limit theorem for k-wise independent random variables.  Rather than attempting an exhaustive list, I hope that the readers who are familiar with a paper using sandwiching polynomials can add a reference in the comments.

I view the technique of sandwiching polynomials as a good example of something simple — it follows immediately from LP duality — which is also extremely useful.

Bazzi has kindly provided  the following text for the second post of the series behind the paper.

 


 

Originally, my objective was to show that the quadratic residues PRG introduced by Alon, Goldreich, Hastad, and Peralta in 1992 looks random to something more powerful than parity functions such as DNF formula or small-width branching programs. My motivation was that the distribution of  quadratic residues promises great derandomization  capabilities. I was hoping to be able to use tools from number theory to achieve this goal.   I worked on this problem for some time, but all the approaches  I tried didn’t use more than what boils down to the small-bias property. In the beginning, my goal was to go beyond this property, but eventually I started to question how far we can go with this property alone in the context of DNF formula. I turned to investigating the question of whether spaces with small-bias  fool DNF formulas, which lead me to the dual question of whether one can construct sandwiching polynomials with low L1-norm in the Fourier domain for DNF formulas. I was not able to use the high frequencies in the Fourier spectrum in the context of DNF formulas. Thus I dropped the low L1-norm requirement and I focused on the simpler low-degree polynomials special case,  which is equivalent to trying to show that limited independence fools DNF formulas. The approaches I  tried in the beginning were based on lifting the k-wise independent probability distribution to the clauses and trying to reduce  the problem  to a LP with  moments constraints. I started to believe that this approach won’t work because  I was ignoring the values of the moments  which are specific to DNF formulas. While  trying to understand the limitations of this approach and researching the related literature, I came across the 1990 paper of Linial and Nisan on approximate inclusion-exclusion,  which excludes the approach I was having trouble with and   conjectures the correctness  of what I was trying to prove.  The attempts I tried later  were all based  on an L2-approximation of the Formula by low-degree polynomials  subject to the constraint that the polynomial is zero on all the zeros of the DNF Formula. The difficulty was in the zeros constraints which  was needed to construct the sandwiching polynomials. Without the zeros constraint, the conjecture would follow from Linial-Mansour-Nisan  energy bound.  I was not hoping that the LMN energy bound can be applied to the problem I was working on since one can construct boolean functions which satisfy the LMN bound  but violates the claim I was after. I was trying to construct the sandwiching polynomials by other methods …
Eventually, I was able to derive many  DNF formulas from the original formula and apply LMN energy bound to each of those formulas to prove the conjecture. Later on, the proof was simplified by Razborov  and extended by Braverman to AC0.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s