Avi Wigderson

Avi Wigderson

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.

The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits of Human Knowledge

Avi Wigderson
Institute for Advanced Study
October 24, 2008

The "P vs. NP" problem is a central outstanding problem of computer science and mathematics.  In this talk, Professor Wigderson attempts to describe its technical, scientific, and philosophical content, its status, and the implications of its two possible resolutions.