The PCP theorem by gap amplificationThe PCP theorem by gap amplification

Access Restriction
Subscribed

 Author Dinur, Irit Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2007 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Gap amplification ♦ PCP Abstract The PCP theorem [Arora and Safra 1998; Arora et. al. 1998] says that every language in NP has a witness format that can be checked probabilistically by reading only a constant number of bits from the proof. The celebrated equivalence of this theorem and inapproximability of certain optimization problems, due to Feige et al. [1996], has placed the PCP theorem at the heart of the area of inapproximability. In this work, we present a new proof of the PCP theorem that draws on this equivalence. We give a combinatorial proof for the NP-hardness of approximating a certain constraint satisfaction problem, which can then be reinterpreted to yield the PCP theorem. Our approach is to consider the unsat value of a constraint system, which is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the underlying variables. We describe a new combinatorial amplification transformation that doubles the unsat-value of a constraint-system, with only a linear blowup in the size of the system. The amplification step causes an increase in alphabet-size that is corrected by a (standard) PCP composition step. Iterative application of these two steps yields a proof for the PCP theorem. The amplification lemma relies on a new notion of “graph powering” that can be applied to systems of binary constraints. This powering amplifies the unsat-value of a constraint system provided that the underlying graph structure is an expander. We also extend our amplification lemma towards construction of assignment testers (alternatively, PCPs of Proximity) which are slightly stronger objects than PCPs. We then construct PCPs and locally-testable codes whose length is linear up to a $\textit{polylog}$ factor, and whose correctness can be probabilistically verified by making a $\textit{constant}$ number of queries. Namely, we prove $\textit{SAT}$ ∈ $\textit{PCP}$ $_{1/2,1}[log_{2}(nṡpoly$ log $\textit{n}),$ $\textit{O}(1)].$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2007-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 54 Issue Number 3

Open content in new tab

Source: ACM Digital Library