[Metric 2011] Prahladh Harsha

-------
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)
-------
Workshop on Metric embeddings, algorithms  and hardness of approximation
January 17-21, 2011
-------
Jan 19, 14:00-15:00
Prahladh Harsha (TIFR Mumbai)
Composition of low-error 2-query PCPs using decodable PCPs
-------
Proof composition is an essential ingredient in all constructions of
probabilistically checkable proofs (PCPs). In this talk, I'll present
a generic, composition method for low error two-query PCPs. This
extends earlier composition methods (such as the ones used in Dinur's
combinatorial construction of PCPs) which were either inapplicable in
the low-error regime or non-modular (i.e., very much tailored to the
specific PCPs that were being composed), if not both. Also,
composition in the low error regime suffered from incurring an extra
consistency query, resulting in PCPs that are not two-query and hence,
much less useful for hardness-of-approximation reductions.

I'll then illustrate how this composition theorem can be used to give
a simple and modular construction of low-error 2-query PCPs of nearly
linear length [Moshkovitz and Raz, 2008]. One of the critical
components in the composition is a variant of PCP called "decodable
PCP". A decodable PCP, besides being locally checkable as a standard
PCP, is also locally decodable, in the sense, that the original NP
witness can be locally decoded from it.

Joint work with Irit Dinur.