MIT
Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
Data Science, Analytics & Computer TechnologyAlgorithms and Data StructuresComputer ScienceScience & MathMathematicsEngineering
Om kurset
In this course, we will present the theory of Probabilistically Checkable Proofs (PCPs), and prove some fundamental consequences of it as well as more recent advances. More specifically, the first half of the course will be devoted to the (algebraic) proof of the basic PCP Theorem and basic relation to approximation problems. We will then move on to more advanced topics, such as hardness amplification, the long-code framework, the Unique-Games Conjecture and its implications, and the 2-to-2 Games Theorem.