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.