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