## 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