Basic Facts about Expander Graphs

DOI10.1007/978-3-642-22670-0_30zbMath1343.68182DBLPbooks/sp/goldreich2011/Goldreich11oOpenAlexW60900481WikidataQ56047332 ScholiaQ56047332MaRDI QIDQ3088196

Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_30

zbMATH Keywords

random walks on graphsexpander graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Random walks on graphs (05C81)

Related Items (3)

Structure indicators for transportation graph analysis. I: Planar connected simple graphs ⋮ Flexibility and movability in Cayley graphs ⋮ The PCP theorem for NP over the reals

Cites Work

• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Ramanujan graphs
• Eigenvalues and expanders
• Explicit constructions of linear-sized superconcentrators
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expander graphs and their applications
• Undirected ST-connectivity in log-space
• Constructive Proofs of Concentration Bounds
• Randomness-Efficient Sampling Within NC 1
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Eigenvalues and expansion of regular graphs
• Computational Complexity

This page was built for publication: Basic Facts about Expander Graphs