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-103
Thursday: DongZhongYuan 1-103

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) slides (printable version).
(2) slides (printable version).
(3) slides (printable version).
(4) slides (printable version).
(5) slides (printable version).
(6) slides (printable version) [RVW, Sec. 4.2].
(7) slides (printable version) [AS; REI].
(8) slides (printable version) [RVW, Sec. 5; GOL, Lect. 2].
(9) slides (printable version) [some notes].
(10) slides (printable version).
(11) slides (printable version).
(12) slides (printable version) [Dinur's paper].
(13) slides (printable version).
(14) slides (printable version).
(15) slides (printable version).
(16) slides (printable version).
(17) slides (printable version).
(18) slides (printable version).


Homework:


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

Back


Yijia Chen, last modified: 25. 11. 2010