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:

Tentative Schedule

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