Academics

  /  

Courses

  /  

Descriptions

COMP_SCI 496: Expander graphs and their applications

VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

EECS 336-0 (or equivalent) and linear algebra. Exposure to abstract algebra and complexity theory would be helpful

Description

Expanders graphs are sparse but well-connected.  These seemingly contrasting properties have led to many applications in theoretical computer science, from complexity theory to hardness of approximation to error correcting codes to super efficient routing networks, and more.  In this course we will discuss various constructions of expander graphs and a few of these applications.  A potential list of topics include the following:

Definitions of expander graphs (edge expansion and spectral expansion), equivalence of definitions, the Alon-Boppana theorem, expansion of random graphs, Margulis's construction, expansion in lifts of graphs, random walks on expanders and applications, Zig-Zag product and SL = L, expander codes, Cayley expander graphs. 

INSTRUCTOR: Prof. Shravas Rao