Charles Simonyi, Chairman of the Institute’s Board of Trustees and President and CEO of Intentional Software Corporation, is the first and only “space tourist” to fly twice: first in 2007 and most recently in 2009, for a combined total of twenty-eight days in space. In this talk, Dr. Simonyi discusses daily life in a spacecraft and on the International Space Station, and shows footage of the dynamic return trip from orbit to the ground in Kazakhstan.
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:
We consider the following two questions:
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.