Paper Info
Title
Composition of Low-Error 2-Query PCPs Using Decodable PCPs
Abstract
Abstract The main result of this paper is a,generic composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well- understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored to the specic PCPs that were being com- posed), resulting in complicated constructions of PCPs. Furthermore, until recently, composition in the low error regime suered,from incurring an extra ‘consistency’ query, resulting in PCPs that are not ‘two-query’ and hence, much less useful for hardness-of-approximation reductions. In a recent breakthrough, Moshkovitz and Raz [In Proc. 49th IEEE Symp. on Foundations of Comp. Science (FOCS), 2008] constructed almost linear-sized low-error 2-query PCPs for every language in NP. Indeed, the main technical component of their construction is a novel composition of certain specic,PCPs. We give a modular and simpler proof of their result by repeatedly applying the new composition theorem to known PCP components. To facilitate the new modular composition, we introduce a new variant of PCP, which we call a decodable PCP (dPCP). A dPCP is an encoding of an NP witness that is both locally checkable and locally decodable. The dPCP verier,in addition to verifying the validity of the given proof like a standard PCP verier, also locally decodes the original NP witness. Our composition is generic in the sense that it works regardless of the way the component PCPs are constructed. A preliminary version of this paper appeared in the Proc. 50th IEEE Symp. on Foundations of Comp. Science
Year
DOI
Venue
2013
10.1109/FOCS.2009.8
Electronic Colloquium on Computational Complexity
Keywords
Field
DocType
specific pcps,component pcps,new composition theorem,certain specific pcps,existing composition method,novel composition,low-error 2-query pcps,decodable pcps,2-query pcps,low error regime,generic composition theorem,new modular composition,composition,probability,probabilistic logic,decoding,computational complexity,polynomials,encoding,robustness,hardness of approximation,indexes,construction industry
Discrete mathematics,Combinatorics,Polynomial,Computer science,Robustness (computer science),Mathematical proof,Probabilistic logic,Decoding methods,Modular design,Encoding (memory),Computational complexity theory
Journal
Volume
Issue
ISSN
42
6
0272-5428
ISBN
Citations 
PageRank 
3-642-16366-1
16
0.60
References 
Authors
27
2
Name
Order
Citations
PageRank
Irit Dinur1118785.67
Prahladh Harsha237132.06