Fall 2007 - Probabilistically Checkable Proofs (236603)

Scribe notes and exercises [PDF, PS]

A lazy instructor wishes to write an exam such that checking it will be easy. The lazy instructor is not willing to read more than 20 (randomly selected) bits from each returned exam, irrespective of its length. The exams should be graded correctly, because every erroneously graded exam will cause the student who wrote it to appeal, costing our poor instructor extra time and agony.

Can our instructor fulfill all these demands? Surprisingly, the answer is yes. This can be achieved if the students are told to write their exams in a so-called "probabilistically checkable" format. This magical proof-format will be the focus of our course. We shall learn how to construct, check and analyze probabilistically checkable proofs. Our working tools come from linear algebra, combinatorics, probablity, harmonic analysis and the theory of error correcting codes.

Main topics:

• The PCP Theorem - statement and main corollaries
• Locally testable and locally decodable codes
• PCPs of proximity (PCPPs) and proof composition
• Soundness amplification via gap amplification and parallel repetition
• Short PCPs based on Reed-Solomon and Reed-Muller codes
• PCPs with near-optimal soundness and query complexity based on long codes

Tentative Schedule

• 21.1.2008    Statement of the theorem, some of its corollaries, and roadmap of the proof.
• 28.1.2008    Two applications of the PCP Theorem: Hardness of approximation and efficient proof checking.
• 4.2.2008      Exponential length PCP I - Hadamrd codes are locally testable.
• 11.2.2008    Exponential length PCP II - Arithmetization of constraint satisfaction problems.
• 18.2.2008    Proof composition of PCPPs (PCPs of proximity)
• 25.2.2008    Length efficient PCP theorem via PCPPs for Reed Solomon codes
• 3.3.2008      Soundness gap amplification using expander graphs - Part I
• 10.3.2008    Soundness gap amplification using expander graphs - Part II
• 17.3.2008    Soundness amplification by parallel repetition - Part I
• 24.3.2008    Soundness amplification by parallel repetition - Part II
• 31.3.2008    Query-soundness optimal PCPs using the long code.
• 7.4.2008      Beyond PCPs - the unique games conjecture.

Links

• Our previous course on the topic (Fall 2005).
• Prahladh Harsha's course on PCPs (Fall 2007).
• Madhu Sudan's lectures on Probabilistically Checkable Proofs.
• Subhash Khot's course on PCPs and hardness of approximation.
• Luca Trevisan's survey on Inapproximability of Combinatorial Optimization Problems .
• Sanjeev Arora and Carsten Lund's survey on Inapproximability.