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