An elementary construction of constant-degree expanders

Noga Mordechai Alon, Oded Schwartz, Asaf Shapira

Research output: Contribution to journalArticle

19 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 1 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