<p>This may be too obvious, but the correctness proof of the Schwartz-Zippel randomized algorithm for polynomial identity testing uses essentially just this fact, plus induction. </p>

CC BY-SA 3.0
2011-09-22T11:25:17.353Z
2011-09-22T11:25:17.353Z
Jan Johannsen
<p>I recently attended a <a href="http://www.cmi.ac.in/~pseudorandom/" rel="nofollow noreferrer">Workshop on Pseudorandomness</a> in <a href="http://www.cmi.ac.in/" rel="nofollow noreferrer">Chennai Mathematical Institute</a> on Pseudorandomness. Venkat Guruswami made the following beautiful statement in passing during his talk (on coding theory):</p>

<blockquote>
  <p>It is remarkable how much one can prove using the simple fact that a
  degree $d$ polynomial over a field can have at most $d$ roots.</p>
</blockquote>

<p>I believe this is also called the Stepanov Method (in those applications, typically roots occur with large multiplicity as well). One place where I've seen this is in <a href="http://arxiv.org/pdf/1104.4557v1" rel="nofollow noreferrer">a paper on square root bounds for the smallest non-residue</a> by Michael Forbes, Neeraj Kayal, Rajat Mittal and Chandan Saha . </p>

<p>This principal was highlighted in the workshop with the unique and list decoding of Reed-Solomon code (<a href="http://www.cs.washington.edu/education/courses/cse533/06au/" rel="nofollow noreferrer">which can be found in this course</a>, for example) in Venkat's talk. In Neeraj Kayal's talk, he gave two other examples -- the proofs of the Finite Field Kakeya Conjecture and the Joints Conjecture (both of which can be found in this <a href="http://www.cs.princeton.edu/~zdvir/papers/Dvir09b.pdf" rel="nofollow noreferrer"> very nice survey</a> by Zeev Dvir). Other examples that I can think of is <a href="http://eccc.hpi-web.de/report/2010/096/" rel="nofollow noreferrer">Dana Moshkovitz's proof of the Schwartz-Zippel Lemma</a>, and another favourite of mine is the <a href="http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf" rel="nofollow noreferrer">AKS Primality test</a> which (if I'm allowed to make a stretch) uses only this fact essentially. </p>

<p>I was wondering if there are other examples of elegant results using (essentially) just this simple fact. </p>

<p>This post is closely related to the earlier question "<a href="https://cstheory.stackexchange.com/questions/2774/polynomial-method-for-complexity-results">Polynomial methods for complexity results</a>" but that was for a more general 'polynomial method'. </p>

CC BY-SA 3.0
2013-01-09T08:45:45.623Z
Actually the "Stepanov method" refers to an elementary proof of Weil's conjecture for curve case. See the book Finite Fields by Rudolf Lidl and Harald Niederreiter.
Zeyu
<reference-request><polynomials>
Results in computer science via the Stepanov method
Ramprasad
# Results in computer science via the Stepanov method

(Asked by: username_0 on 2011-09-22)

I recently attended a [Workshop on Pseudorandomness](http://www.cmi.ac.in/~pseudorandom/) in [Chennai Mathematical Institute](http://www.cmi.ac.in/) on Pseudorandomness. Venkat Guruswami made the following beautiful statement in passing during his talk (on coding theory):

> It is remarkable how much one can prove using the simple fact that a
> degree $d$ polynomial over a field can have at most $d$ roots.

I believe this is also called the Stepanov Method (in those applications, typically roots occur with large multiplicity as well). One place where I've seen this is in [a paper on square root bounds for the smallest non-residue](http://arxiv.org/pdf/1104.4557v1) by Michael Forbes, Neeraj Kayal, Rajat Mittal and Chandan Saha .

This principal was highlighted in the workshop with the unique and list decoding of Reed-Solomon code ([which can be found in this course](http://www.cs.washington.edu/education/courses/cse533/06au/), for example) in Venkat's talk. In Neeraj Kayal's talk, he gave two other examples -- the proofs of the Finite Field Kakeya Conjecture and the Joints Conjecture (both of which can be found in this  [very nice survey](http://www.cs.princeton.edu/~zdvir/papers/Dvir09b.pdf) by Zeev Dvir). Other examples that I can think of is [Dana Moshkovitz's proof of the Schwartz-Zippel Lemma](http://eccc.hpi-web.de/report/2010/096/), and another favourite of mine is the [AKS Primality test](http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf) which (if I'm allowed to make a stretch) uses only this fact essentially.

I was wondering if there are other examples of elegant results using (essentially) just this simple fact.

This post is closely related to the earlier question "[Polynomial methods for complexity results](https://cstheory.stackexchange.com/questions/2774/polynomial-method-for-complexity-results)" but that was for a more general 'polynomial method'.

**Tags:** reference-request, polynomials

> **Comments:**
> **username_1**: Actually the "Stepanov method" refers to an elementary proof of Weil's conjecture for curve case. See the book Finite Fields by Rudolf Lidl and Harald Niederreiter.  

---

## 1 answers

### Answer by username_2 on 2011-09-22. Score: 4

This may be too obvious, but the correctness proof of the Schwartz-Zippel randomized algorithm for polynomial identity testing uses essentially just this fact, plus induction.


---

