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.
Thoughts 