## Subsampling Mathematical Relaxations and Average-case Complexity

We consider the following two questions:

Boaz Barak

Institute for Advanced Study

May 24, 2010

We consider the following two questions:

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:

Amir Yehudayoff

Institute for Advanced Study

May 11, 2010

Dana Moshkovitz

Institute for Advanced Study

April 27, 2010

Vijay Vazirani

Georgia Institute of Technology

April 19, 2010

*It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest. Each participant in a competitive economy is led by an invisible hand to promote an end which was no part of his intention.*

Adam Smith, 1776

Eyal Lubetzky

Microsoft Research Redmond

April 13, 2010

James Lee

University of Washington

April 12, 2010

The cover time of a graph is one of the most basic and well-studied properties of the simple random walk, and yet a number of fundamental questions concerning cover times have remained open. We show that there is a deep connection between cover times of graphs and Talagrand's majorizing measure theory. In particular, we prove that the cover time can be characterized, up to universal constants, by the majorizing measure value of a certain metric space on the underlying graph.

Peter Sarnak

Institute for Advanced Study

April 6, 2010

Mark Braverman

Microsoft Research New England

April 6, 2010

Valentine Kabanets

Simon Fraser University; Institute for Advanced Study

March 30, 2010

We give a simple combinatorial proof of the Chernoff-Hoeffding concentration

bound for sums of independent Boolean random variables. Unlike the standard

proofs, our proof does not rely on the method of higher moments, but rather uses

an intuitive counting argument. In addition, this new proof is constructive in the

following sense: if the given random variables fail the concentration bound, then

we can efficiently find a subset of the variables that are statistically dependent.