Assignment Testing and PCPs
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.