Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-119 | 13th September 2006 00:00

An Elementary Construction of Constant-Degree Expanders

RSS-Feed




TR06-119
Authors: Noga Alon, Oded Schwartz, Asaf Shapira
Publication: 13th September 2006 16:05
Downloads: 3477
Keywords: 


Abstract:

We describe a short and easy to analyze construction of
constant-degree expanders. The construction relies on the
replacement-product, which we analyze using an elementary
combinatorial argument. The construction applies the replacement
product (only twice!) to turn the Cayley expanders of \cite{AR},
whose degree is polylog n, into constant degree
expanders.



ISSN 1433-8092 | Imprint