Tuesday, April 19, 2005

A New PCP Proof

There is some buzz about a new construction of probabilistically checkable proofs by Irit Dinur. The PCP theorem, first proved by Arora, Lund, Motwani, Sudan and Szegedy in the early 90's, states that every language in NP has a proof that can be verified randomly using O(log n) random bits and a constant number of queries. The PCP theorem has had many applications to showing hardness of approximation results and has had many improvements such as Håstad's tight result that I highlighted last year.

The previous proofs used considerable algebraic techniques. Dinur takes a more combinatorial approach using a powering and composition technique (inspired by Reingold and the zig-zag product) to separate the gap in 3SAT without increasing the number of variables.

An upcoming STOC paper by Ben-Sasson and Sudan gives a PCP for SAT of only quasilinear size but requiring polylogarithmic queries to verify the proof. Dinur, by applying her construction to those PCPs, can now create quasilinear-size proofs which only need a constant number of queries for verification.


  1. When reproving a known result TWO questions
    come to mind (maybe three, Maybe more)

    1) Is the new proof DIFFERENT
    (in this case it seems to be yes)

    2) Is the new proof EASIER
    (Can't tell. The abstract stresses
    that its combinatorial and self-contained
    but didn't say easier. Maybe thats one of
    those Pet Peeves someone has-- don't say
    its an easier proof, thats for the reader
    to decide.)

    3) Does it yield NEW corollaries
    (in this case seems to be yes)

    An EASIER proof of a known important result is VALUBALE, and I hope this
    is such. If so, I may finally get
    to teach the entire PCP theorem in
    my complexity class.

  2. I don't see why (3) is so important. Simpler proofs are good for many reasons, including teaching. The faster we can pass knowledge to our students, the sooner they can start doing original work.