Expander Graphs, Lifts, and Applications

Abstract

Expander graphs are a central object of study in theoretical computer science for their applications in derandomization, deterministic error reduction, constructing error correcting codes, and many other areas. Informally, expanders are d-regular graphs which are sparse yet well-connected globally; though random d-regular graphs are known to be good expanders in expectation, finding deterministic constructions of expanders, which are required in most applications, is much more difficult. In this report, we introduce expander graphs as an object of study, and give an exposition of commonly used techniques to analyze expander graphs, particularly their spectrum. Then, we introduce the lift operation on graphs, explore some of its properties, and survey recent literature utilizing lifts to generate families of expander graphs. Finally, we analyze a recent paper of Cohen and Cohen, which utilizes a natural extension of lifts called the partial lift to interpolate between graphs in a known expander family, and create intermediaries which are themselves good spectral expanders and have limited differences from the previous family member.