Using sampling to get from one expander to another

Sampling is the problem of using randomness to approximate the average of a
function.  The Chernoff bound tells us that, by choosing a small random set S
of inputs, we can estimate the average over the entire input domain with
exponentially small probability of deviation.  Usually the function considered
is real-valued; Ahlswede-Winter showed that there is an analogue of the
Chernoff bound for matrix-valued functions, i.e. functions mapping to real
symmetric d x d matrices.

In this talk we will show how to improve the randomness-efficiency of sampling
matrix-valued functions by taking the samples according to a random walk on an
expander graph.  This idea was introduced by Ajtai-Komlos-Szmeredi and was
shown by Gillman to perform essentially as well as independent samples for
real-valued functions.  Our results thus extend both Ahlswede-Winter and
Gillman.

We will then show how to apply this sampler to the problem of Alon-Roichman:
given an arbitrary group H, find a set S of size O(log n) such that the Cayley
graph Cay(H; S) is a good expander.  Alon-Roichman showed this is possible by
random sampling; we apply our sampler to get a poly-time deterministic
algorithm.

Finally we will discuss the main ideas behind the proof that our sampler
achieves exponentially small probability of deviation.  Our main technical
results relies on facts from perturbation theory, an interesting field of
analysis that we believe may be relevant to theoretical computer scientists in
other ways.

This is joint work with Avi Wigderson.