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 language | English (US) |
---|---|
Pages (from-to) | 319-327 |
Number of pages | 9 |
Journal | Combinatorics Probability and Computing |
Volume | 17 |
Issue number | 3 |
DOIs | |
State | Published - May 2008 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics