Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOSSLESS EXPANDER:
Reports tagged with Lossless Expander:
TR23-089 | 15th June 2023
Louis Golowich

New Explicit Constant-Degree Lossless Expanders

Revisions: 1

We present a new explicit construction of onesided bipartite lossless expanders of constant degree, with arbitrary constant ratio between the sizes of the two vertex sets. Our construction is simpler to state and analyze than the prior construction of Capalbo, Reingold, Vadhan, and Wigderson (2002).

We construct our ... more >>>




ISSN 1433-8092 | Imprint