The Zig-Zag Product and Expansion Close to the Degree

Salil Vadhan
Harvard University

We will describe how the zig-zag product can be used to construct explicit constant-degree expander graphs with expansion (1-epsilon)*degree for an arbitrarily small constant epsilon. Previously, the largest expansion achieved was degree/2, attained by Ramanujan graphs, and it was known that bounds on the second eigenvalue alone cannot do better. Indeed, our result is obtained by analyzing the zig-zag product for "randomness conductors", which measure expansion through a combination of min-entropy and statistical distance (ie L-infinity and L-one norms) rather than eigenvalues (ie L-two norm).

Joint work with Michael Capalbo, Omer Reingold, and Avi Wigderson

Presentation (PowerPoint File)

Back to Automorphic Forms, Group Theory and Graph Expansion