29
$\begingroup$

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?

$\endgroup$
29
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ Wow... so many amazing results!! These are truly awesome, thank you very much!! $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 9 '10 at 5:12
20
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.