Entropy waves, the zig-zag graph product, and new constant-degree

Omer Reingold, Salil Vadhan, Avi Wigderson

The main contribution of this work is a new type of graph product, which we call the {\it zig-zag product}. Taking a product of a large graph with a small graph, the resulting grap…