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