Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > REPLACEMENT PRODUCT:
Reports tagged with replacement product:
TR24-089 | 8th May 2024
Gil Cohen, Itay Cohen, Gal Maor

Tight Bounds for the Zig-Zag Product

The Zig-Zag product of two graphs, $Z = G \circ H$, was introduced in the seminal work of Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound, which is used throughout, states that the spectral expansion of ... more >>>




ISSN 1433-8092 | Imprint