Computer Science/Discrete Mathematics Seminar II

Expander graphs are sparse and yet well-connected graphs. Several applications in theoretical computer science require explicit constructions of expander graphs, sometimes even with additional structure. One approach to their construction is to start from a small expander and apply (once or several times) a well-known lifting operation to obtain a larger expander. In this talk, we will describe an explicit (near-Ramanujan) construction of lifted expander graphs possessing an additional large symmetry structure. The analysis boils down to a more careful counting argument building on the incredible progress seen in this kind of construction. The additional symmetry structure of our lifted expanders has applications to coding theory.

This is based on joint work with Tushant Mittal, Ryan O'Donnell, Pedro Paredes and Madhur Tulsiani.