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

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

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• 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
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Ramanujan graphs
• Randomness-Efficient Sampling Within NC 1
• Undirected ST-connectivity in log-space

Cited in

(7)

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

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)