Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors
Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors
The main contribution is a new type of graph product, which we call the zig-zag product. Taking a product of a large graph with a small graph, the resulting graph inherits (roughly) its size from the large one, its degree from the small one, and its expansion properties from both. …