Expander graphs and their applications

2006/08/07 by Shlomo Hoory, Nathan Linial, Avi Wigderson · 6 citations
Computer Science · Engineering · #Advanced Graph Theory Research #graph theory and CDMA systems #Graph Labeling and Dimension Problems

paper · pdf · doi:10.1090/s0273-0979-06-01126-8

openalex publication_date 2006/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, come up in numerous and often surprising contexts in both fields.

Citations

• Filling Riemannian manifolds
• Eigenvalues and expanders
• A product decomposition for the classical quasisimple groups
• A Mathematical Theory of Communication
• Random Cayley graphs and expanders
• An algorithm for the machine calculation of complex Fourier series
• Inequalities in Fourier Analysis
• Probabilistic checking of proofs; a new characterization of NP
• Deterministic simulation in LOGSPACE
• Proof verification and hardness of approximation problems
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Explicit unique-neighbor expanders
• Lectures on Discrete Geometry
• On the Distribution of the Roots of Certain Symmetric Matrices
• Kazhdan Constants for SL_n(Z)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks

Cited by

• Proving expansion in three steps
• Monotone Circuits for the Majority Function
• List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
• The Nature of Computation
• Overlap properties of geometric expanders
• Expander graph [wikipedia]
• Isoperimetric inequality [wikipedia]