Abstract

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