Fall 2005 - From error correcting codes to inapproximability via Probabilistically Checkable Proofs (236610)

Scribe notes (Lectures 1-12) [PDF, postscript]

Probablisitically Checkable Proofs (PCPs) are proofs whose validity can be verified very efficiently (by inspecting a few random bits of the proof). PCPs have numerous applications to error correcting codes, cryptography and hardness of approximation. In this course we will prove the PCP Theorem and describe some of its applications. Special focus will be given to concepts and tools of "general interest" used in the consrtuction and investigation of PCPs.

Main topics:

• The PCP Theorem
  • History and importance. 
  • Basic ingredients: locally testable codes (LTCs) and PCPs of Proximity (PCPPs).
  • Exponential length PCPPs (based on Hadamard codes).
  • PCPP composition.
  • Polynomial length PCP (Dinur's gap amplification).
• Length-efficient PCPs
  • Algebraic PCPs (based on polynomials).
  • Efficient low degree testing.
  • Applications to Error Correcting Codes.
• Run-time efficient PCPs
  • Poly-logarithmic verification.
  • Applications to cryptographic verification of programs.
• Query-efficient PCPs
  • Connection to Inapproximability.
  • Soundness reduction and Raz's parallel repetition Theorem.
  • The long code and its analysis.
  • Hastad's tight inapproximability results.
  • Khot's unique games conjecture and its applications.

Tentative Schedule

• 3.11.05    History and basic definitions (Verifier and PCP). Statement of the (state of the art) PCP Theorem .
• 10.11.05  The Hadamard code is locally testable.
• 17.11.05  All linear properties of a message can be locally decoded from the Hadamard code
• 24.11.05  An exponentially long Hadamard based PCP.
• 1.12.05    Dinur's proof by gap amplification - expanderizing.
• 8.12.05    Alphabet reduction by composition with PCPPs
• 15.12.05  The gap amplification lemma.
• 22.12.05  Towards short PCPs - Reed-Solomon codes
• 29.12.05  Short PCPPs for Reed-Solomon codes over binary fields.
• 5.1.06      Algebraic constraint satisfaction problems.
• 12.1.06    PCPs with small query complexity and large soundness - Raz's parallel repetition Theorem.
• 19.1.06    Towards tight inapproximability results - the long code.
• 26.1.06    Hastad's long-code based results.
• 2.2.06      Beyond PCPs - Khot's unique games conjecture.

Exercises

1. Basic PCP transformations [PDF, postscript].  Due 17.11.2005.
2. Limitations of gap amplification [PDF, postscript].  Due 15.12.2005.
3. PCPPs for RS-codes; Parallel repetition [PDF, postscript].  Due 19.1.2006.
4. Fourier analysis of Hastad's long-code based PCP [PDF, postscript].  Due 2.2.2006.

Links

• 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.