Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
The PCP theorem and hardness of approximation, including low-degree testing, long codes, parallel repetition and the Unique-Games Conjecture.
Some NP-hard problems stay NP-hard even when you only want an answer close to the optimum, and proving that requires the PCP theorem. This class presents the theory of probabilistically checkable proofs, starting with an algebraic proof of the basic theorem. It then moves to hardness amplification, the long-code framework, the Unique-Games Conjecture and the 2-to-2 Games Theorem.
What You Will Achieve
- Follow the algebraic proof of the basic PCP Theorem
- Use error correcting codes and low-degree testing in proof constructions
- Derive hardness of approximation results for clique and set cover
- Explain the Unique-Games Conjecture and its link to Max-cut
Program Overview
The Basic PCP Theorem
The first half builds the proof from coding and algebraic tools.
- Error correcting codes
- The sum-check protocol
- Low-degree testing
- Hadamard codes and composition
Hardness of Approximation
Next the theorem is applied, and repetition makes the results stronger.
- Hardness of approximating the maximum clique
- The Parallel Repetition Theorem
- Reduction from label-cover to set-cover
Long Codes and Unique Games
The closing lectures reach optimal results and a major conjecture.
- The long-code paradigm
- Optimal inapproximability results
- The Unique-Games Conjecture
- Goemans-Williamson algorithm and Max-cut
Course Completion
Job Outlook
This theory serves research in theoretical computer science, particularly on approximation and complexity.
Good for: Theory students and researchers who want a full treatment of PCPs and hardness of approximation, with hard starred problems to test themselves.
Keep in mind: The materials are lecture notes and five problem sets, with no solutions listed and no videos.
Bottom line: A focused route through the PCP theorem and its consequences, closing on more recent advances.
Frequently Asked Questions
What are the starred problems?
The five problem sets mix problems of normal difficulty with more challenging ones marked with a star. Normal problems were enough for an A-, and higher grades needed a substantial number of starred ones.
Where can I find related material?
The syllabus names online courses by Subhash Khot at NYU, Irit Dinur and Dana Moshkovitz at the Weizmann Institute, and Alessandro Chiesa at Berkeley.
Does it cover recent results?
Yes. The description lists the 2-to-2 Games Theorem among the advanced topics, along with hardness amplification and the Unique-Games Conjecture and its implications.



There are no reviews yet.