Computer Science/Discrete Mathematics Seminar II

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