Dive into a comprehensive lecture on Probabilistically Checkable Proofs (PCP) delivered by Dana Moshkovitz from the University of Texas at Austin. Explore the PCP Theorem, global properties, and the formulation of PCP in P language. Examine the differences between global and local tests, and delve into computational problems. Learn about simple and complex constructions, linear functions, variables, and equations related to PCP. This 78-minute talk, part of the Probability, Geometry, and Computation in High Dimensions Boot Camp at the Simons Institute, provides a thorough crash course on this important topic in computational complexity theory.
Crash Course on Probabilistically Checkable Proofs - PCP
Overview
Syllabus
Introduction
PCP Theorem
Global Properties
Can PCP be formulated in P language
Global vs Local Tests
Computational Problem
Simple Construction
Construction
Linear Functions
Variables
Equations
Conclusion
Proof
Taught by
Simons Institute
