IP = PSPACE - Graduate Complexity Lecture at CMU

Explore the groundbreaking theorem IP = PSPACE in this graduate-level complexity theory lecture from Carnegie Mellon University. Delve into interactive proof systems, the "Going My Prime" protocol, and the relationship between Merlin and Arthur. Examine univariate polynomials, instance checkers, and the concept of Merlin as an oracle. Learn from Professor Ryan O'Donnell's comprehensive coverage of this advanced topic, complementing the Arora-Barak textbook chapters 8.3 and 8.4. Gain a deeper understanding of computational complexity theory and its implications in this 79-minute video lecture, part of CMU's Fall 2017 course 15-855.

Introduction
General Scenario
Interactive Proof Systems
Going My Prime
Interactive Proof
Protocol
Univariate polynomial
Motivation
Merlin
Arthur
Interlude
Sharp P
Instance checkers
Interactive proofs vs instance checkers
Merlin as an Oracle