Seminar

There is a well-known connection between the expansion of a graph and its second largest eigenvalue. Motivated by connections to the Unique Games Conjecture, recent research has focused on the expansion of small sets of vertices in a graph and its spectrum.

A graph G is a small-set expander if sufficiently small sets in the graph have near perfect expansion. A recent result by Arora, Barak and Steurer (ABS) shows that a small-set expander cannot have too many (polynomial in |V|) large eigenvalues. The noisy hypercube shows that the number can be at least logarithmic in the |V|. ABS raise the question of determining the right bound.

We show how to construct small-set expanders which have many more large eigenvalues than the noisy hypercube. Our construction draws a connection between the spectrum of the Cayley graph of a code, and the local testability of its dual code. If time permits, we will discuss some implications for algorithmic problems like Unique Games and Max-Cut.

Joint work with Boaz Barak (MSR-NE), Johan Hastad (KTH), Raghu Meka (UT Austin), Prasad Raghavendra (GaTech) and David Steurer (MSR-NE).