Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

The Stepanov Method

Avi Wigderson
Institute for Advanced Study
May 25, 2010

The Stepanov method is an elementary method for proving bounds on the number of roots of polynomials. At its core is the following idea. To upper bound the number of roots of a polynomial f(x) in a field, one sets up an auxiliary polynomial F(x) , of (magically) low degree, which vanishes at the roots of f with high multiplicity. That appropriate F exits is usually proved by a dimension argument.