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.