An Elementary Construction of Constant-Degree Expanders

COMPUTER SCIENCE/DISCRETE MATH II
Topic:An Elementary Construction of Constant-Degree Expanders
Speaker:Oded Schwartz
Affiliation:Tel-Aviv University
Date:Tuesday, January 16
Time/Room:10:30am - 12:30pm/S-101

We describe a short and easy-to-analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold et. al. [2002] to give an iterative construction of bounded-degree expanders. Here we give a simpler construction, which uses the replacement product (only twice) and turns 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 new simple combinatorial analysis of the replacement product (instead of the spectral analysis used in Reingold et. al. [2002]). Joint work with Noga Alon and Asaf Shapira