Completed
Hardness of Approximation
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Smoothed Complexity of 2-player Nash Equilibria
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Pause and Reflect
- 3 Question for today
- 4 Big Picture
- 5 Smoothed Analysis
- 6 Smoothed Algorithmica
- 7 Hardness of Approximation
- 8 Finding a Nash Equilibrium
- 9 Quick work on PPAD
- 10 Back to Nash
- 11 Algorithms for Nash
- 12 Smoothed Nash
- 13 Outline
- 14 Proof Overview
- 15 Reduction Step 1: Padding Alice
- 16 Reduction Step 2: Zero-sum noise
- 17 Full Reduction
- 18 Key facts about Nash equlibria
- 19 Large support
- 20 Small lz norm
- 21 concentration
- 22 Recap: Analysis in 3 steps
- 23 Conclusion
