## Expander graphs: applications and constructions (a mini-course of
3 lectures)

by Avi Wigderson

#### Oded's comments

I was only in the third lecture in this mini-series.
As usual, Avi's talks are packed with information
and I learned quite a lot,
although this material is within my sphere of interests.

One thing I learned about is an old work of Babai et al.,
which refers to the problem of generating an almost uniformly
distributed elememt in a group that is given by a set of generators
(and an oracle to the group operation).
The generated group (or rather its Cayley graph) is not necessarily expanding,
although the number of elements in it can be exponential
in the length of the descryption of the generator set.
For example, if the group generated by $g_1,...,g_t$ is Abelian,
then sequences of length $\ell$ yield less than $\ell^t$ possible elements
(since the element generated depends only on the number of occurances
of each generator in the sequence, regardless of their location).
This also shows that, in general, we cannot hope to generate a random element
as a product of a small number of occurances of the generators,
since such representation may not exist for most elements in the group.
Instead, random (or generic) elemenmts are represented as short
straightline program over the set of generators.

The basic idea of the random generation algorithm
is to iteratively generate at random a sample of the elements
in the "Cube" of the current sample, where the cube of $x_1,...,x_t$
is defined as all $2^{2t}$ subproducts
of the product $x_t^{-1} ... x_1^{-1}x_1 ... x_t$
(i.e., a generic element in the cube is has the form $y_t ... y_1 z_1 ... z_t$,
where $y_i\in\{\id, x_i^{-1}\}$ and $z_i\in\{\id,x_i\}$).
This iterative step is repeated for a number of times that is
logarithmic in the size of the group
(i.e., polynomial in the given representation).

#### The original slides

See
www.math.ias.edu/~avi/TALKS/expander_tutorial_June2010.ppt

Back to
list of Oded's choices.