Completed
Hardness of Promise-true NP-Search
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Is it Easier to Prove Statements that are Guaranteed to be True?
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Worst-case vs Average-case Hardness
- 3 Challenger - Solver game G89,195
- 4 Hardness of Promise-true NP-Search
- 5 Promise-true NP-Search problems
- 6 Machine Learning: Local Search JPY'88
- 7 Nash Equilibrium
- 8 Open Problem 1
- 9 Restricted Distributions: One-way functions
- 10 Open Problem 2
- 11 Average-case Hardness of NP [K73,L86]
- 12 Main Theorem
- 13 Proof Overview
- 14 Interactive Puzzles
- 15 2-round Puzzles
- 16 Main Question
- 17 Failure of Babai-Moran Transformation for computational soundness
- 18 Main Lemma: If a OWF, BM-transformation works
- 19 Concluding the proof
- 20 Concluding Remarks
