Mathematical Sciences Research Institute

Home » Small-Set Expansion from Local Testability: derandomizing the noisy hypercube


Small-Set Expansion from Local Testability: derandomizing the noisy hypercube September 08, 2011 (02:00 PM PDT - 03:00 PM PDT)
Parent Program: --
Location: MSRI: Simons Auditorium
Speaker(s) Parikshit Gopalan (MSR Silicon Valley)
Description No Description
No Video Uploaded

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).

No Notes/Supplements Uploaded No Video Files Uploaded