An elementary construction of constant-degree expanders

Noga Alon; Oded Schwartz; Asaf Shapira

An elementary construction of constant-degree expanders

Noga Alon, Oded Schwartz, Asaf Shapira

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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

Original language	English (US)
Title of host publication	Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Publisher	Association for Computing Machinery
Pages	454-458
Number of pages	5
ISBN (Electronic)	9780898716245
State	Published - 2007
Externally published	Yes
Event	18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States Duration: Jan 7 2007 → Jan 9 2007

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	07-09-January-2007

Other

Other	18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Country/Territory	United States
City	New Orleans
Period	1/7/07 → 1/9/07

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@inproceedings{9b7cfec3c49c4866bd0eafcff92e8af1,

title = "An elementary construction of constant-degree expanders",

abstract = "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]).",

author = "Noga Alon and Oded Schwartz and Asaf Shapira",

note = "Publisher Copyright: Copyright {\textcopyright} 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.; 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 ; Conference date: 07-01-2007 Through 09-01-2007",

year = "2007",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "454--458",

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

}

Alon, N, Schwartz, O & Shapira, A 2007, An elementary construction of constant-degree expanders. in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 07-09-January-2007, Association for Computing Machinery, pp. 454-458, 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, United States, 1/7/07.

An elementary construction of constant-degree expanders. / Alon, Noga; Schwartz, Oded; Shapira, Asaf.
Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, 2007. p. 454-458 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 07-09-January-2007).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - An elementary construction of constant-degree expanders

AU - Alon, Noga

AU - Schwartz, Oded

AU - Shapira, Asaf

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 -

An elementary construction of constant-degree expanders

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this