Recently Added

Reductions Between Expansion Problems

Madhur Tulsiani
Institute for Advanced Study
May 18, 2010

The small-set expansion conjecture introduced by Raghavendra and Steuerer is a natural hardness assumption concerning the problem of approximating edge expansion of small sets (of size $\delta n$) in graphs. It was shown to be intimately connected to the well-known Unique Games Conjecture.

Pursuing this line of research further, we obtain the following results:

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.

Quanta, Symmetry, and Topology

Frank Wilczek
Herman Feshbach Professor of Physics, Massachusetts Institute of Technology
September 24, 2010

Quantum theory radically transforms our fundamental understanding of physical reality. It reveals that the world contains a hidden richness of  structure that we have barely begun to control and exploit. In this lecture, Frank Wilczek indicates the extraordinary potential ofquantum engineering (the size and nature of Hilbert space); reviews one important ongoing effort to harness it (topological quantum computing); and speculates on its ultimate prospects (quantum minds).

This lecture was part of the Institute for Advanced Study’s celebration of its eightieth anniversary, and took place during the events related to the Schools of Mathematics and Natural Sciences.