Polynomial method for complexity results 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?
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.