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
Links