Abstract:

Expander graphs are essential tools in a variety of combinatorial
and algorithmic problems. We give nearly sharp representation theoretic
conditions on a group G which guarantee the existence of highly symmetric
expanders in the group algebra F_p[G]. This and related results
are applied to a problem in coding theory and lead to a new construction of
expanding Cayley graphs of nearly constant degree.
Joint work with A. Wigderson .