Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with graph products:
TR01-018 | 23rd February 2001
Omer Reingold, Salil Vadhan, Avi Wigderson

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

The main contribution of this work 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 ... more >>>

ISSN 1433-8092 | Imprint