Back to Courses
Advanced
Software Development
en
Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
MIT OpenCourseWare
Platform
· Cambridge, USA
About this course
In this graduate-level course, students are introduced to the theory of Probabilistically Checkable Proofs (PCPs) and its major consequences in theoretical computer science and approximation algorithms. The first half of the course focuses on the algebraic proof of the basic PCP Theorem and its fundamental relation to approximation problems. The second half covers more advanced topics, including hardness amplification, the long-code framework, the Unique Games Conjecture and its implications, and the 2-to-2 Games Theorem.
Prerequisite Skills
Skills you should have before taking this course
Discrete mathematics
Abstract algebra
Algorithms and data structures
Probability theory
Introduction to theoretical computer science
advanced discrete mathematics
mathematical maturity
Skills Gained
Skills you will develop by completing this course
Theoretical computer science
Computational complexity theory
Probabilistically Checkable Proofs (PCP)
Approximation algorithms
Hardness of approximation
Unique Games Conjecture
Long code techniques
Mathematical proofs
Discrete mathematics
computational complexity