<p>There is Zeev Dvir's result on the <strong>finite field Kakeya problem</strong> 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. </p>

<p>Zeev's result was motivated by the task of constructing <strong>randomness extractors</strong>. 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. </p>

<p>See more in Zeev's survey: <a href="http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf">http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf</a></p>

CC BY-SA 2.5
2010-11-09T05:14:03.583Z
I did not notice this connection before, thanks!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-08T21:35:16.747Z
2010-11-11T13:20:30.660Z
2010-11-11T13:20:30.660Z
Dana Moshkovitz
<p>Some classic examples of the use of the polynomial method are:</p>

<ul>
<li>Razborov-Smolensky's proof of "Parity not in $AC^0$" (<a href="http://www.google.com/search?sclient=psy&amp;hl=en&amp;source=hp&amp;q=razborov+parity">lots</a> of expositions available online, <a href="http://people.csail.mit.edu/madhu/ST05/scribe/lect06.ps">here is one</a>)</li>
<li>Beigel-Reingold-Spielman's proof of <a href="http://portal.acm.org/citation.cfm?id=103426">"PP is closed under intersection"</a></li>
<li><a href="http://people.cs.uchicago.edu/~razborov/files/bazzi.pdf">Bazzi's result for fooling DNFs</a>, and Braverman's proof of "<a href="http://www.cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf">Polylog independence fools $AC^0$</a>"</li>
</ul>

<p>Also, fourier analysis of boolean functions (<a href="http://www.cs.cmu.edu/~odonnell/boolean-analysis/">here is a great course by Ryan O'Donnell</a>)  has a HUGE collection of awesome results, my favourite being the Kushilevitz-Mansour-Nisan's <a href="http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture7.pdf">proof of the Goldreich-Levin theorem</a>. </p>

<p>Scott Aaronson had in fact given a tutorial at FOCS'08 on the "<a href="http://www.scottaaronson.com/talks/polymeth.ppt">The Polynomial Method in Classical and Quantum Computing (ppt)</a>". </p>

<p>Hope this helps.</p>

CC BY-SA 2.5
2010-11-09T05:12:10.980Z
Wow... so many amazing results!! These are truly awesome, thank you very much!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-08T08:30:44.390Z
2010-11-08T08:30:44.390Z
Ramprasad
<p><strong>Polynomial methods</strong>, say <a href="https://www.tau.ac.il/%7Enogaa/PDFS/null2.pdf" rel="nofollow noreferrer">Combinatorial Nullstellensatz</a> and <a href="http://alpha.math.uga.edu/%7Epete/4400ChevalleyWarning.pdf" rel="nofollow noreferrer">Chevalley–Warning theorem</a> 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 <a href="https://en.wikipedia.org/wiki/Restricted_sumset" rel="nofollow noreferrer">restricted sumsets</a> or <a href="https://en.wikipedia.org/wiki/Zero-sum_problem" rel="nofollow noreferrer">zero-sum problems</a>, and some of the theorems in this area can be proved only by such methods.</p>
<p>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).</p>
<blockquote>
<p>Are there any complexity results known that one can prove them by polynomial methods?</p>
</blockquote>

<cc.complexity-theory><reference-request><co.combinatorics><polynomials>
Polynomial method for complexity results
Hsien-Chih Chang 張顯之
# Polynomial method for complexity results

(Asked by: username_0 on 2010-11-08)

**Polynomial methods**, say [Combinatorial Nullstellensatz](https://www.tau.ac.il/%7Enogaa/PDFS/null2.pdf) and [Chevalley–Warning theorem](http://alpha.math.uga.edu/%7Epete/4400ChevalleyWarning.pdf) 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](https://en.wikipedia.org/wiki/Restricted_sumset) or [zero-sum problems](https://en.wikipedia.org/wiki/Zero-sum_problem), 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?

**Tags:** cc.complexity-theory, reference-request, co.combinatorics, polynomials

---

## 2 answers

### Answer by username_2 on 2010-11-08. Score: 29 | Accepted answer

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

* Razborov-Smolensky's proof of "Parity not in $AC^0$" ([lots](http://www.google.com/search?sclient=psy&hl=en&source=hp&q=razborov+parity) of expositions available online, [here is one](http://people.csail.mit.edu/madhu/ST05/scribe/lect06.ps))
* Beigel-Reingold-Spielman's proof of ["PP is closed under intersection"](http://portal.acm.org/citation.cfm?id=103426)
* [Bazzi's result for fooling DNFs](http://people.cs.uchicago.edu/~razborov/files/bazzi.pdf), and Braverman's proof of "[Polylog independence fools $AC^0$](http://www.cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf)"

Also, fourier analysis of boolean functions ([here is a great course by Ryan O'Donnell](http://www.cs.cmu.edu/~odonnell/boolean-analysis/)) has a HUGE collection of awesome results, my favourite being the Kushilevitz-Mansour-Nisan's [proof of the Goldreich-Levin theorem](http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture7.pdf).

Scott Aaronson had in fact given a tutorial at FOCS'08 on the "[The Polynomial Method in Classical and Quantum Computing (ppt)](http://www.scottaaronson.com/talks/polymeth.ppt)".

Hope this helps.

> **Comments:**
> **username_0**: Wow... so many amazing results!! These are truly awesome, thank you very much!!  

---

### Answer by username_1 on 2010-11-08. Score: 20

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>

> **Comments:**
> **username_0**: I did not notice this connection before, thanks!!  

---

