Expanders that beat the eigenvalue bound

DOI10.1145/167088.167163zbMath1310.68168OpenAlexW1999736539MaRDI QIDQ5248492

David Zuckerman, Avi Wigderson

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167163

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Extractors for weak random sources and their applications ⋮ Simulating BPP using a general weak random source ⋮ Low-degree test with polynomially small error ⋮ Construction of expanders and superconcentrators using Kolmogorov complexity ⋮ Hamiltonian paths in Cayley graphs ⋮ Extracting randomness: A survey and new constructions ⋮ Storing information with extractors.

This page was built for publication: Expanders that beat the eigenvalue bound