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.
When reproving a known result TWO questions
ReplyDeletecome 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.
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.
ReplyDelete