Eigenvalues, expanders and superconcentrators

Noga Alon, V. D. Milman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Explicit construction of families of linear expanders and superconcentrators is relevant to theoretical computer science in several ways. There is essentially only one known explicit construction. Here we show a correspondence between the eigenvalues of the adjacency matrix of a graph and its expansion properties, and combine it with results on Group Representations to obtain many new examples of families of linear expanders. We also obtain better expanders than those previously known and use them to construct explicitly n-superconcentrators with ≃157.4 n edges, much less than the previous most economical construction.

Original languageEnglish (US)
Title of host publication25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PublisherIEEE Computer Society
Pages320-322
Number of pages3
ISBN (Electronic)081860591X
StatePublished - 1984
Externally publishedYes
Event25th Annual Symposium on Foundations of Computer Science, FOCS 1984 - Singer Island, United States
Duration: Oct 24 1984Oct 26 1984

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1984-October
ISSN (Print)0272-5428

Conference

Conference25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Country/TerritoryUnited States
CitySinger Island
Period10/24/8410/26/84

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Eigenvalues, expanders and superconcentrators'. Together they form a unique fingerprint.

Cite this