Expanders that beat the eigenvalue bound: Explicit construction and applications

DOI10.1007/S004930050049zbMath0929.05075OpenAlexW2611055803MaRDI QIDQ1125612

David Zuckerman, Avi Wigderson

Publication date: 8 December 1999

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004930050049

zbMATH Keywords

graphsexpanderconnectorsorting algorithmselection algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15)

Related Items (12)

Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Constant time parallel sorting: An empirical view. ⋮ Expander graphs and their applications ⋮ Deterministic extractors for small-space sources ⋮ An Introduction to Randomness Extractors ⋮ Rainbow paths ⋮ Extractors from Reed-Muller codes ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ Interactive Communication, Diagnosis and Error Control in Networks ⋮ Multicast Routing and Design of Sparse Connectors ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

This page was built for publication: Expanders that beat the eigenvalue bound: Explicit construction and applications