EIGENVALUES, EXPANDERS AND SUPERCONCENTRATORS.

Noga Alon, V. D. Milman

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

40 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, a correspondence is shown between the eigenvalues of the adjacency matrix of a graph and its expansion properties, and this result is combined with results on group representations to obtain many new examples of families of linear expanders. Better expanders than those previously known are obtained and used to construct explicitly n-superconcentrators with congruent 157. 4n edges, much less than the previous most economical construction.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages320-322
Number of pages3
ISBN (Print)081860591X
StatePublished - Dec 1 1984
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'EIGENVALUES, EXPANDERS AND SUPERCONCENTRATORS.'. Together they form a unique fingerprint.

Cite this