PCPs of sub-constant error via derandomized direct product
Speaker: Or Meir , Weizmann Institute
Date: October 20 2009
Time: 4:15PM to 5:15PM
Location: 32-155
Contact: be, 3-6098, imbe@mit.edu
Relevant URL:
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 on PCPs will be assumed.
Joint work with Irit Dinur.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in October 2009
