Basic Facts about Expander Graphs

DOI10.1007/978-3-642-22670-0_30MaRDI QIDQ3088196zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

expander graphsrandom walks on 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)

Cites work

• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Computational Complexity
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Constructive proofs of concentration bounds
• Eigenvalues and expanders
• Eigenvalues and expansion of regular graphs
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expander graphs and their applications
• Explicit constructions of linear-sized superconcentrators
• Ramanujan graphs
• Randomness-Efficient Sampling Within NC 1
• Undirected ST-connectivity in log-space
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(6)

• The PCP theorem for NP over the reals
• Flexibility and movability in Cayley graphs
• Computing the edge expansion of a graph using semidefinite programming
• A construction of random bigraphs and their application to error correction codes
• Structure indicators for transportation graph analysis. I: Planar connected simple graphs
• Derandomization with pseudorandomness

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

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