Overview
Syllabus
Intro
Worst-case vs Average-case Hardness
Challenger - Solver game G89,195
Hardness of Promise-true NP-Search
Promise-true NP-Search problems
Machine Learning: Local Search JPY'88
Nash Equilibrium
Open Problem 1
Restricted Distributions: One-way functions
Open Problem 2
Average-case Hardness of NP [K73,L86]
Main Theorem
Proof Overview
Interactive Puzzles
2-round Puzzles
Main Question
Failure of Babai-Moran Transformation for computational soundness
Main Lemma: If a OWF, BM-transformation works
Concluding the proof
Concluding Remarks
Taught by
IEEE FOCS: Foundations of Computer Science