Completed
Worst-case versus Average-case complexity
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Two mysteries of complexity theory
- 3 Main Theorem
- 4 Worst-case versus Average-case complexity
- 5 Efficiently Samplable Distribution
- 6 Landscape of Average-case Complexity
- 7 Outline
- 8 Variants of MINKT MINKTA: an A-oracle version of MINKT Input
- 9 Open Questions on Meta-Complexity
- 10 Meta-Complexity versus Average-Case Complexity
- 11 Corollary Errorless hardness amplification for PH
- 12 Summary and an Open Question
