An elementary construction of constant-degree expanders

Noga Alon, Oded Schwartz, Asaf Shapira

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

4 Scopus citations

Abstract

We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by [14] to give an iterative construction of bounded-degree expanders. Here we give a simpler construction, which applies the replacement product (only twice!) to turn the Cayley expanders of [4], whose degree is polylog n, into constant degree expanders. This enables us to prove the required expansion using a new simple combinatorial analysis of the replacement product (instead of the spectral analysis used in [14]).

Original languageEnglish (US)
Title of host publicationProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PublisherAssociation for Computing Machinery
Pages454-458
Number of pages5
ISBN (Electronic)9780898716245
StatePublished - Jan 1 2007
Externally publishedYes
Event18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States
Duration: Jan 7 2007Jan 9 2007

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume07-09-January-2007

Other

Other18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
CountryUnited States
CityNew Orleans
Period1/7/071/9/07

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'An elementary construction of constant-degree expanders'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Schwartz, O., & Shapira, A. (2007). An elementary construction of constant-degree expanders. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 (pp. 454-458). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 07-09-January-2007). Association for Computing Machinery.