Expander Graphs in Computer Science

Expander Graphs in Computer Science

Advanced Course 48876

Annooucement:

Final Exam Date: Feb. 8
Please check General Remarks of Exam (Jan. 12)
No class in Feb. (Jan. 25)
There is an all-in-one version of the lecture notes. (Feb. 1)

Lecturer	Dr. He Sun Email: hsun@mpi-inf.mpg.de Office: Campus E1 4, Room 325 Phone: 681 9325 125 Office Time: Monday 15:00-16:00
Time and Location	Tuesday 14:00-16:00 Lecture Room 003, Campus E1. 3
Final Exam	Tuesday Feb. 8. General Remarks
Credits	6 ECTS points
Syllabus	syllabus
Script	script

Course Topics

Introduction to expanders
Algebraic graph theory
Random walks, Chernoff bounds for expander walks
Expander codes
Pseudorandon generators

Reference: [Nis92]

Combinatorial constructions of expanders

Reference: [RVW02]

Reingold's unconditional derandomization of symmetric logspace

Reference: [Rei08]

Extractors
Condensers
The unified theory

Reference: [Vad07]

Lectures

[Oct. 19] Lecture 1: Introduction to Expander Graphs

[Oct. 26] Lecture 2: Algebraic Definition of Expander Graphs

Lecture Notes

[Nov. 2] Lecture 3: Random Walks on Expanders

Lecture Notes

[Nov. 9] Lecture 4: Expanders Codes

Lecture Notes

[Nov. 23] Lecture 5: Construction of Expanders

Lecture Notes
Referene: Reingold et al.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. Annals of Maths. 155:157-187, 2002.

[Nov. 30] Lecture 6: Undirected Connectivity in Log-Space

Lecture Notes
Reference: Reingold: Undirected connectivity in log-space. Journal of the ACM, 55(4):17, 2008

[Dec. 7] Lecture 7: Pseudorandom Generators (I)

Lecture Notes

[Dec. 14] Lecture 8: Pseudorandom Generators (II)

Lecture Notes

[Jan. 4] Lecture 9: Randomness Extractors

Lecture Notes

[Jan. 11] Lecture 10: Lossless Conductors

Lecture Notes
Reference: Capalbo et al. Randomness conductors and constant-degree lossless expanders. In: Proc. of the 34th STOC. pp. 659-668, 2002

[Jan. 18] Lecture 11: List-Decodable Codes

Lecture Notes

[Jan. 25] Lecture 12: The Unified Theory of Pseudorandomness

Lecture Notes
Referenec: Vadhan. The unified theory of pesudorandomness. ACM SIGACT News, 38(3):39-54, September 2007.

Assignments

Problem Set 1

pdf file
Solutions pdf file

Problem Set 2

pdf file
Solutions pdf file

Problem Set 3

pdf file

Grading

Homework 60% (3 problem sets), Final exam 40% (Oral exam)
You need to collect at least 50% of the homework points to be eligible to take the final exam.

Results

No.	Grade
2535471	1.3
2534438	2
2535467	2.3
2020519	3.7
2026439	5
2030493	5

References

[CRV02] M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson. Randomness conductors and constant-degree lossless expanders. In: Proc. of the 34th STOC. pp. 659-668, 2002
[Din07] I. Dinur. The PCP theorem by gap amplification. Journal of the ACM, 55(3):12, 2007.
[HLW06] S. Horry, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006.
[Nis92] N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992.
[Rei08] O. Reingold: Undirected connectivity in log-space. Journal of the ACM, 55(4):17, 2008
[RVW02] O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. Annals of Maths. 155:157-187, 2002.
[Vad07] S. Vadhan. The unified theory of pesudorandomness. ACM SIGACT News, 38(3):39-54, September 2007.