TY - GEN

T1 - An elementary construction of constant-degree expanders

AU - Alon, Noga

AU - Schwartz, Oded

AU - Shapira, Asaf

N1 - Publisher Copyright:
Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.

PY - 2007

Y1 - 2007

N2 - 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]).

AB - 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]).

UR - http://www.scopus.com/inward/record.url?scp=84857610746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84857610746&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84857610746

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 454

EP - 458

BT - Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007

PB - Association for Computing Machinery

T2 - 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007

Y2 - 7 January 2007 through 9 January 2007

ER -