A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product

DOI10.1137/080732651zbMATH Open1222.05147OpenAlexW2015393836WikidataQ62398455 ScholiaQ62398455MaRDI QIDQ3020006FDOQ3020006

Amnon Ta-Shma, Avraham Ben-Aroya

Publication date: 29 July 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080732651

zbMATH Keywords

expander graphscombinatorial constructionzig-zag product

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cited In (6)

• Explicit expanders of every degree and size
• Paradigms for Unconditional Pseudorandom Generators
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Deterministic Tensor Completion with Hypergraph Expanders
• Random walks on rotating expanders
• Explicit Near-Ramanujan Graphs of Every Degree

This page was built for publication: A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3020006)