Course Announcement

Expanders Graphs: Constructions and Applications

Time: Mon 14:00-15:30 and 16:00-17:30
Location: G77
Instructors : and
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2015-16/expanders/

Expanders Graphs: Constructions and Applications

Over the past several decades, expander graphs have played a pervasive role in diverse fields of mathematics and computer science - network design, derandomization, distributed computing, random walks, error-correcting codes, metric embeddings etc. Informally, an expander is a sparse graph which is nevertheless highly connected. In this course, we will study these expander graphs, their constructions and several of their applications. We will study various ways of constructing expanders and their applications

Constructions

• Property T and Property tau for semisimple Lie groups
• Margulis' explicit construction of expander graphs
• Ramanujan graphs
• construction of Lubotzky-Philips-Sarnak
• Expanders from finite linear groups - the Bourgain-Gamburd argument
• zig-zag expanders.
• Random lifts (Bilu-Linial, Marcus-Spielman-Srivastava)

Applications

• Derandomization
  (including Reingold's "SL=L" result)
• Error Correcting Codes
• Metric embeddings
• Dinur's proof of the PCP Theorem

Instructors : and

Prahladh Harsha