Computer Science/Discrete Mathematics Seminar I

A PCP is a proof system in which the proofs that can be verified by a verifier that reads only a very small part of the proof. One line of research concerning PCPs is trying to reduce their soundness error (i.e., the probability of accepting false claims) as much as possible. In particular, using low-degree curves, it is possible to construct PCP verifiers that use only two queries and have soundness error that is an inverse poly-logarithmic function in the input length. In this talk, we show a an alternative construction of such PCPs, using a simpler and less algebraic approach. This is done by extending the derandomized direct product test of Impagliazzo, Kabanets and Wigderson (STOC 09) to a construction of a PCP. To that end, we identify general properties of a PCP that allow amplifying its soundness by the means of direct product. We then show that any PCP can be transformed into one that achieves those general properties by embedding the corresponding constraint graph on a de-Bruijn graph. No prior knowledge of PCPs will be assumed. (This is joint work with Irit Dinur.)