Probabilistic Checking of Proofs (PCPs)

Outline of a 2-module course to be taught at the Scuola Matematica Interuniversitaria.

July 3-15, 2005 & July 18-29, 2005.

The modern theory of computation has come up with radically novel notions of (verification of) proofs. These notions emerge from allowing the verifier to toss a few coins (so they are not deterministic); and allowing the verifiers to err with a small probability. The PCP theorem, proved in the early 90s, asserts that there exist probabilistic verifiers that look at purported proofs of assertions in just a constant number of bits and reject any proof of invalid assertions with probability at least half, while accepting valid proofs of theorems with probability one. Furthermore, these probabilistically checkable proofs are only slightly (polynomially) longer than any standard proof of the theorem. In addition to the inherent interest in such strikingly easy verification processes, PCPs have also been very useful in estabilishing ``inapproximability'' results. Specifically, for many classical optimization problems, the PCP theorem implies that finding near-optimal solutions is as hard as finding optimal solutions. In the two modules we will cover the PCP theorem and its many ``optimal'' versions, as also several of the inapproximability consequences.

Module 1 (July 3-15): The PCP Theorem

The goal of this module is to come up with the definition of PCPs, and then to show the PCP theorem, while also covering some simple consequences to approximability of optimization problems. The proof of the PCP theorem we will cover is a new one, due to Irit Dinur. Central ingredients in the proof are (1) The connection between PCPs and approximation of "Constraint Satisfaction" problems, (2) Algebraic techniques in complexity theory, and (3) Techniques used to reduce randomness in randomized algorithms. Rough contents of lectures will be as follows:

  1. Proofs and Complexity, Definition of PCP. Notes.
  2. Optimization and Complexity, Approximability and Inapproximability, PCPs and Inapproximability of Max CSP. Notes.
  3. Inapproximability of Max Clique. Amplification of PCPs. Consequence to Max Clique. Notes.
  4. An exponentially long proof of SAT with constant query complexity - I. Notes.
  5. An exponentially long proof of SAT with constant query complexity - II. Notes.
  6. Linearity testing; conclusion of analysis of construction of lecture 4.
  7. Outline of Dinur's proof of the PCP theorem: PCPs and Max CSP.
  8. Step 2 of Dinur's proof: Reducing alphabet size in Max CSP using the exponentially long PCPs for SAT.
  9. Step 1 of Dinur's proof: A technique for amplifying gap in Max CSP at the cost of larger alphabets.
  10. Analysis of Step 1. Concluding remarks.
Reading Materials: Since the proof is quite new, there are few sources for most of the details. Basic definitions and the connection to approximability (lectures 1-3) are covered in many works, cf. [1]. The exponentially long proof of SAT can be read from [2, Sections 5 and 6] or [1]. The analysis of the linearity test can be found, e.g., in [3, Section 2]. Dinur's proof of the PCP theorem (Lectures 7-10) can be found in her original work [4].
  1. Madhu Sudan. Lecture Notes from a mini-course on PCPs, scribed by Venkatesan Guruswami.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. JACM, 45(3): 501--555, May 1998.
  3. Michael Ben-Or, Don Coppersmith, Michael Luby and Ronitt Rubinfeld. Non-Abelian Homomorphism Testing and Distributions close to their self-convolutions. Proceedings of RANDOM 2004.
  4. Irit Dinur. The PCP Theorem via Gap Amplification. ECCC TR05-46.
Module 2: Optimzing parameters of the PCP Theorem

Note: This module assumes very little of the techniques of the first module. However there is a strong (and necessary) overlap in the motivation. The first lecture in the course will provide a quick review of the main definitions and results of the first module that will be used in the second one.

In this module we focus on some essential parameters of PCPs: Namely the query complexity, the soundness, and the length of PCPs. We describe some of the results leading to optimal and near-optimal tradeoffs between these parameters. Once again some of these questions are motivated by the inherent interest in PCPs, and others by the implications to inapproximability. Tentative breakdown of topics (more coarse than in Module 1) is given below:
  1. Recap of definition of PCPs and the PCP theorem. Parameters.
  2. Optimizing soundness while minimizing query complexity - I
  3. Optimizing soundness while minimizing query complexity - II
  4. Optimizing soundness ... - III; Implications to Max 3SAT.
  5. Optimizing soundness for large query complexity - I
  6. Optimizing soundness for large query complexity - II
  7. Optimizing soundness ... - III; Implications to Max Clique.
  8. Optimizing length of proofs - I
  9. Optimizing length of proofs - II
  10. Optimizing length of proofs -III; Conclusions.
Reading materials: Lectures 2-4 are based on [1,2]. Lectures 5-7 are based on [3,4,5,6]; Lectures 8-10 are based on [7,8].
  1. Ran Raz. A Parallel Repetition Theorem. SIAM Journal on Computing, 27(3):763--803, 1998.
  2. Johan Håstad. Some optimal inapproximability results. JACM, 48:798--859, 2001.
  3. Johan Håstad. Clique is hard to approximate to within n^1-epsilon. Acta Mathematica, 182:105--142, 1999.
  4. Madhu Sudan and Luca  Trevisan. Probabilistically Checkable Proofs with Low Amortized Query Complexity. Proc. FOCS, pp. 18-27, 1998.
  5. Alex Samorodnitsky and Luca Trevisan. A PCP Characterization of NP with Optimal Amortized Query Complexity. Proc. STOC, pp. 191-199, 2000.
  6. Johan Håstad and Avi Wigderson. Simple analysis for linearity and PCP, Manuscript, 2002.
  7. Eli Ben-Sasson and Madhu Sudan. Simple PCPs with Poly-log Rate and Query Complexity. ECCC TR04-060.
  8. Irit Dinur. The PCP Theorem via Gap amplification. ECCC TR05-46.


Author: Madhu Sudan