| 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