Fall 2007 - Probabilistically Checkable
Scribe notes and exercises [PDF,
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.
- 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
- 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
- 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
- 7.4.2008 Beyond PCPs - the unique games