Polynomial method for complexity results

Question

Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee the existence of a solution, or the number of solutions to the polynomials. They have been used to solve problems like restricted sumsets or zero-sum problems, and some of the theorems in this area can be proved only by such methods.

To me the non-constructive manner of these methods are truly amazing, and I'm curious about that how we can apply these methods to prove any interesting inclusions and separations of complexity classes (even if the result can be solved by other methods).

Are there any complexity results known that one can prove them by polynomial methods?

Answer 1

Some classic examples of the use of the polynomial method are:

• Razborov-Smolensky's proof of "Parity not in $AC^0$" (lots of expositions available online, here is one)
• Beigel-Reingold-Spielman's proof of "PP is closed under intersection"
• Bazzi's result for fooling DNFs, and Braverman's proof of "Polylog independence fools $AC^0$"

Also, fourier analysis of boolean functions (here is a great course by Ryan O'Donnell) has a HUGE collection of awesome results, my favourite being the Kushilevitz-Mansour-Nisan's proof of the Goldreich-Levin theorem.

Scott Aaronson had in fact given a tutorial at FOCS'08 on the "The Polynomial Method in Classical and Quantum Computing (ppt)".

Hope this helps.

Answer 2

There is Zeev Dvir's result on the finite field Kakeya problem that was mentioned on this website before. Zeev used the polynomial method to lower bound the number of points in any set of points in F^n (F finite field, n natural number) that contains a line in every direction. This result actually drew attention of people in analysis to the polynomial method.

Zeev's result was motivated by the task of constructing randomness extractors. This is part of a huge effort in theoretical computer science to derandomize algorithms, and ultimately show that P=BPP and similar complexity results hold.

See more in Zeev's survey: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf