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