## Expander Graphs and Applications

**Instructor**:

**Yijia Chen**

**Time**:

8:00am - 9:40am every **second** Tuesday

10:00am - 11:40am every Thursday

**Place**:

Tuesday: DongZhongYuan 1-202

Thursday: DongZhongYuan 4-105

**Reference**:

**[AS]** N. Alon and B. Sudakov,

**
Bipartite Subgraphs and the Smallest Eigenvalue**.

*Combinatorics, Probability and Computing, 9, pp. 1-12, 2000. *

**[GOL]** O. Goldreich,

**
Randomized Methods in Computation**.

*Lecture Notes, 2001. *

**[HLW]** S. Hoory, N. Linial, and A. Wigderson,

**
Expander Graphs and their Applications**.

*Bulletin of Amererican Mathematical Society, 43, pp 439-561, 2006. *

**[REI]** O. Reingold,

**
Undirected ST-Connectivity in Log-Space**.

*STOC, 2005. *

**[RVW]** O. Reingold, S. Vadhan, and A. Wigderson,

**
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders**.

*Annals of Mathematics, vol. 155, no.1, pp. 157-187, 2002. *

**Slides**:

(1) 17/09/2009
(for printing).

(2) 22/09/2009
(for printing).

(3) 24/09/2009
(for printing).

(4) 10/10/2009
(for printing).

(5) 15/10/2009
(for printing).

(6) 20/10/2009
(for printing) [**RVW**, Sec. 4.2].

(7) 22/10/2009
(for printing) [**AS**; **REI**].

(8) 29/10/2009
(for printing) [**RVW**, Sec. 5; **GOL**, Lect. 2].

(9) 03/11/2009
(for printing)
[**some notes**].

(10) 05/11/2009
(for printing).

(11) 12/11/2009
(for printing).

(12) 16/11/2009
(for printing)
[**Dinur's paper**].

(13) 19/11/2009
(for printing).

(14) 26/11/2009
(for printing).

(15) 1/12/2009
(for printing).

(16) 3/12/2009
(for printing).

(17) 10/12/2009
(for printing).

(18) 29/12/2009
(for printing).

(19) 31/12/2009
(for printing).

(20) 7/1/2010
(for printing).

**Homework**:

To view the *ps* and *pdf* files, you need
**GSview**
and **Acrobat Reader**.

Back

*Yijia Chen*, *last modified*: 10. 12. 2009