Explicit expanding expanders

DOI10.1007/s00453-016-0269-xzbMath1372.68208arXiv1507.01196OpenAlexW3034792725MaRDI QIDQ2408170

Asaf Valadarsky, Michael Dinitz, Michael Schapira

Publication date: 10 October 2017

Published in: Algorithmica, Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.01196

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Explicit expanding expanders ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Lifts, discrepancy and nearly optimal spectral gap
• Explicit construction of linear sized tolerant networks
• Ramanujan graphs
• The isoperimetric number of random regular graphs
• Explicit constructions of linear-sized superconcentrators
• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Explicit expanding expanders
• DEX: self-healing expanders
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• Novel architectures for P2P applications