REVIEW 1 cited by
New Explicit Constant-Degree Lossless Expanders
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original 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.
Forward citations
Cited by 1 Pith paper
-
Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
An explicit infinite family of biregular graphs is shown to have (3/5 - epsilon)-two-sided unique-neighbor expansion, the first to beat the spectral 0.5d barrier.
Discussion (0). Continue with ORCID to comment.