Assignment Testing and PCPs
Would anyone like to improve their understanding of the PCP Theorem? This is, in my opinion, the most amazing result in all of computer science, and with the recent work of Irit Dinur its proof should be within reach of a much larger audience. However, there is still considerable complexity involved.
I recently finished writing an expository paper called Building Assignment Testers that presents one key step in Dinur's proof, the step which is most algebraic and most indebted to previous PCP constructions. In my paper I state the PCP Theorem, build and analyze 'assignment testers', and explain why this step is also sufficient to give a weaker version of the PCP Theorem, in which the proof string supplied by the prover is not required to be polynomially bounded.
Several good references are available already, but in the paper I explain why I hope my work represents an expository advance. Essentially, I aim to make clearer how assignment testing can be viewed as a natural composition of simple statistical tests, and how these tests can be first analyzed in isolation, then combined by a general lemma.
For anyone who saw and enjoyed my talk on Property Testing, or read the Powerpoint, Assignment Testers are an important and very interesting application of the testing paradigm--a natural next step for study.
Enjoy the paper! Of course, I welcome questions and comments.
I recently finished writing an expository paper called Building Assignment Testers that presents one key step in Dinur's proof, the step which is most algebraic and most indebted to previous PCP constructions. In my paper I state the PCP Theorem, build and analyze 'assignment testers', and explain why this step is also sufficient to give a weaker version of the PCP Theorem, in which the proof string supplied by the prover is not required to be polynomially bounded.
Several good references are available already, but in the paper I explain why I hope my work represents an expository advance. Essentially, I aim to make clearer how assignment testing can be viewed as a natural composition of simple statistical tests, and how these tests can be first analyzed in isolation, then combined by a general lemma.
For anyone who saw and enjoyed my talk on Property Testing, or read the Powerpoint, Assignment Testers are an important and very interesting application of the testing paradigm--a natural next step for study.
Enjoy the paper! Of course, I welcome questions and comments.
Labels: complexity
posted by Andy D at
2:36 PM
6 Comments:
Typo, paragraph 5 (concerning the soundness property). Should read "if $x \not \in L$, currently reads if $x \in L$.
David Speyer
By
Anonymous, at 3:17 PM
Thanks, David! I'll try to correct all typos pointed out to me.
By
Andy D, at 4:20 PM
I'd like to see an argument for why the PCP theorem is the "most amazing result in all of computer science". People say this, or something similar, a lot of the time, without explaining why. It's certainly technically interesting, and it is a little surprising, but results such as Valiant-Vazirani, Immerman-Szelepcsenyi and Shor are far more susprising.
By
Anonymous, at 2:48 AM
Thanks, Cheshire, that's a valid point. It's a commonly voiced opinion, and the popularity of PCP has presumably influenced my own judgment, though it's not an opinion I adopted overnight or without critical thought.
I will try to make my case, or rather explain how I arrived at this opinion (since not every factor will 'make a claim' on readers) with respect to the theorems you mentioned, with the provisos that
i) I don't fully understand Shor's proof, and while I've understood Dinur's proof piece-by-piece, I've never been able to fit the entire thing in my head all at once except in outline;
ii) It's a subjective opinion, and you're free to adopt your own.
OK, here goes.
First, Shor. Shor's result is amazing. And I'm sure I would be more enamored of it if I had more passion for number theory and/or quantum mechanics. As it is, I'm looking in from without. In the same way, I'm sure that topologists are more amazed by what Perelman achieved than I am, even though they were in a much better position to achieve it themselves. To me, it looks like someone patched up the n = 3 case of something in topology.
From a complexity perspective, PCP has one big thing over Shor: generality/scope. It applies to all NP problems, and provides a new format for deductive proofs in general.
It also says something unexpected about how knowledge can be transmitted between two parties, and as such it has implications for the shape of possible social realities. And people are closer to the heart of my own mathematical imagination than numbers or physics.
Shor's result impacts the possibility of cryptography, which has even more social relevance, but its impact is contingent on the feasibility of QC and on the existence/nonexistence of non-factoring-based secure cryptosystems. I'm fairly agnostic on both counts, but the real issue for me is that factoring hasn't been (to my mind) drawn compellingly enough into the 'storyline' of complexity theory to really grab me.
(break)
By
Andy D, at 2:42 PM
PCP has one definite thing over Valiant-Vazirani and Immerman-Szelepcsenyi: the latter two results, ingenious though they assuredly are, also seem simple in retrospect. It's difficult for me to see them with fresh eyes. On the other hand, as much as I hope to reach a point where PCPs seem truly simple, I'm not sure I'll ever get there.
PCP has also been, I think, far more fertile in terms of the research it has spawned (in approximability of algorithms). Here, however, I'll admit that its applications to complexity theory proper (as opposed to algorithms) has been less important than one might've hoped; the ideas of Valiant-Vazirani have, I think, performed better in this regard. (by the way, I've been vaguely planning a post on V-V, and would happily consider any specific questions and suggestions about it.)
Finally, there is a technical reason why PCP (and other results of the Interactive Proofs 'revolution') stands apart for me: whereas V-V is part of the long line of structural complexity theory results that amount to algorithms manipulating exponentially-large strings implicitly generated by NP machines in a black-box fashion (i.e. assuming nothing about the string that might follow from the way it is generated), the PCP theorem attacks a concrete NP-complete problem (3-SAT originally, constraint graphs with Dinur) using powerful mathematical tools that tie in in a specific way (arithmetization and statistical algebraic tests originally, expanders with Dinur).
Not only is this kind of step provably necessary to bypass the limits of relativizing arguments, it is incredibly 'refreshing' from a mathematical perspective in a way that I can't really explain. But fifteen years later, I think there is still a widespread sense that the PCP theorem is the closest thing we have to an image of the future for complexity theory.
By
Andy D, at 3:04 PM
Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.
By
Coach Factory Online, at 2:49 AM
Post a Comment
<< Home