Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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:

Cover Times, Blanket Times, and Majorizing Measures

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.

A Combinatorial Proof of the Chernoff-Hoeffding Bound, With Applications to Direct-Product Theorems

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.