Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics, gave a Friends Forum in October 2011, entitled Randomness and Pseudo-randomness. Is the universe inherently deterministic or probabilistic? Perhaps more importantly, can we tell the difference between the two?
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 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.