[MPRI 2014] 1.24 Algorithmes randomisés (Cours n°4 - Partie C/C)
Nicolas Schabanel
2014-02-18
Views 46
MPRI 1.24 - Randomized Algorithms - Nicolas Schabanel
Lecture 4 (Part C/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
Lecture 4 (Part C/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
Report form
RELATED VIDEOS
