Measuring Shape With Homology

Robert MacPherson
Institute for Advanced Study
April 7, 2010

The ordinary homology of a subset S of Euclidean space depends only on its topology. By systematically organizing homology of neighborhoods of S, we get quantities that measure the shape of S, rather than just its topology. These quantities can be used to define a new notion of fractional dimension of S. They can also be effectively calculated on a computer.

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.