Computational Complexity

Tuesday, April 19, 2005

 
A New PCP Proof

Posted by Lance

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.

6:52 AM #

1.  GASARCH says:  
   
   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:39 PM, April 19, 2005

2.  Anonymous says:  
   
   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.
   

   10:08 PM, April 19, 2005