An elementary construction of constant-degree expanders

Noga Alon, Oded Schwartz, Asaf Shapira

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

We describe a short and easy-to-analyse construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold, Vadhan and Wigderson (2002) 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 Alon and Roichman (1994), whose degree is polylog n, into constant-degree expanders. This enables us to prove the required expansion using a simple new combinatorial analysis of the replacement product (instead of the spectral analysis used by Reingold, Vadhan and Wigderson).

Original languageEnglish (US)
Pages (from-to)319-327
Number of pages9
JournalCombinatorics Probability and Computing
Volume17
Issue number3
DOIs
StatePublished - May 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

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

Cite this