Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Is it Easier to Prove Statements that are Guaranteed to be True?

IEEE via YouTube

Overview

Explore the intriguing question of whether statements guaranteed to be true are easier to prove in this 26-minute IEEE conference talk by Rafael Pass from Cornell Tech and Muthuramakrishnan Venkitasubramaniam from the University of Rochester. Delve into topics such as worst-case vs. average-case hardness, the Challenger-Solver game, and the hardness of Promise-true NP-Search problems. Examine machine learning concepts, including local search and Nash Equilibrium, before tackling open problems related to restricted distributions and one-way functions. Investigate the average-case hardness of NP, interactive puzzles, and the failure of the Babai-Moran Transformation for computational soundness. Gain insights into the main theorem, its proof overview, and the concluding remarks that tie together these complex concepts in computational theory.

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

Reviews

Start your review of Is it Easier to Prove Statements that are Guaranteed to be True?

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.