Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-089 | 9th January 2024 06:37

New Explicit Constant-Degree Lossless Expanders

RSS-Feed




Revision #1
Authors: Louis Golowich
Accepted on: 9th January 2024 06:37
Downloads: 43
Keywords: 


Abstract:

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 only prior construction of Capalbo, Reingold, Vadhan, and Wigderson (2002), and achieves improvements in some parameters.

We construct our lossless expanders by imposing the structure of a constant-sized lossless expander "gadget" within the neighborhoods of a large bipartite spectral expander; similar constructions were previously used to obtain the weaker notion of unique-neighbor expansion. Our analysis simply consists of elementary counting arguments and an application of the expander mixing lemma.



Changes to previous version:

Edits to exposition


Paper:

TR23-089 | 15th June 2023 09:02

New Explicit Constant-Degree Lossless Expanders





TR23-089
Authors: Louis Golowich
Publication: 15th June 2023 09:20
Downloads: 501
Keywords: 


Abstract:

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 lossless expanders by imposing the structure of a constant-sized lossless expander "gadget" within the neighborhoods of a large bipartite spectral expander; similar constructions were previously used to obtain the weaker notion of unique-neighbor expansion. Our analysis simply consists of elementary counting arguments and an application of the expander mixing lemma.



ISSN 1433-8092 | Imprint