Video Lectures

We consider the following two questions:

1. Is the MAX-CUT problem hard on random geometric graphs of the type considered by Feige and Schechtman (2002)?
   
2. Is the value of a mathematical relaxation such as semi-definite programming (SDP) for a constraint...

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...

An epsilon-biased set X in {0,1}n is a set so that for every non-empty set T in [n] the following holds. The random bit B(T) obtained by selecting at random a vector x in X, and computing the mod-2 sum of its T-coordinates, has bias at most...

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...

Bethlehem, Pennsylvania, was founded in the 1740s as a utopian religious community. At the turn of the twentieth century, it became one of the iconic steel towns of industrial America, a destination for working-class immigrants and the producer of...