[MPRI 2014] 1.24 Algorithmes randomisés (Cours n°4 - Partie B/C)

MPRI 1.24 - Randomized Algorithms - Nicolas Schabanel

Lecture 4 (Part B/C) Thursday Feb 13, 8:45-11:45 - Expander graphs
• Expansion: Combinatoric definition
• Expansion: Spectral definition
• Cheeger inequalities and first applications
• Expander constructions: Examples and Zig-Zag product

Exercise session 4:
• Zig-zag product
• Graph constraints satisfaction Gap-problem: Degree uniformization step
• Random walks on expanders are almost sequences of independent trials