{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,10,16]],"date-time":"2021-10-16T09:04:54Z","timestamp":1634375094056},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,6]]},"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.<\/jats:p>\n 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.<\/jats:p>\n \n Our approach is to consider the\n unsat value<\/jats:italic>\n 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.\n <\/jats:p>\n The amplification lemma relies on a new notion of \u201cgraph powering\u201d 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.<\/jats:p>\n \n 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\n polylog<\/jats:italic>\n factor, and whose correctness can be probabilistically verified by making a\n constant<\/jats:italic>\n number of queries. Namely, we prove\n SAT<\/jats:italic>\n \u2208\n PCP<\/jats:italic>\n 1\/2,1<\/jats:sub>\n [log\n 2<\/jats:sub>\n (\n n<\/jats:italic>\n \u22c5poly log\n n<\/jats:italic>\n ),\n O<\/jats:italic>\n (1)].\n <\/jats:p>","DOI":"10.1145\/1236457.1236459","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"12","source":"Crossref","is-referenced-by-count":186,"title":["The PCP theorem by gap amplification"],"prefix":"10.1145","volume":"54","author":[{"given":"Irit","family":"Dinur","sequence":"first","affiliation":[{"name":"The Hebrew University, Jerusalem, Israel"}]}],"member":"320","reference":[{"key":"e_1_2_2_1_1","unstructured":"Arora S. 1994. Probabilistic checking of proofs and the hardness of approximation problems. Ph.D. dissertation U.C. Berkeley. (Available via anonymous ftp as Princeton TR94-476.) Arora S. 1994. Probabilistic checking of proofs and the hardness of approximation problems. Ph.D. dissertation U.C. Berkeley. (Available via anonymous ftp as Princeton TR94-476.)"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22192"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007361"},{"key":"e_1_2_2_8_1","volume-title":"RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science.","author":"Ben-Sasson E."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_2_2_10_1","unstructured":"Bogdanov A. 2005. Gap amplification fails below 1\/2. Comment on ECCC TR05-046 can be found at http:\/\/eccc.uni-trier.de\/eccc-reports\/2005\/TR05-046\/commt01.pdf. Bogdanov A. 2005. Gap amplification fails below 1\/2. Comment on ECCC TR05-046 can be found at http:\/\/eccc.uni-trier.de\/eccc-reports\/2005\/TR05-046\/commt01.pdf."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.16"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225183"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90251-8"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(02)00024-6"},{"key":"e_1_2_2_16_1","unstructured":"Goldreich O. 1997. A sample of samplers a computational perspective on sampling. Electronic Colloquium on Computational Complexity TR97-020. Goldreich O. 1997. A sample of samplers a computational perspective on sampling. Electronic Colloquium on Computational Complexity TR97-020."},{"key":"e_1_2_2_17_1","volume-title":"RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science, Springer-Verlag","author":"Goldreich O."},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Goldreich O."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4%3C315::AID-RSA3%3E3.0.CO;2-1"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 18th Annual Symposium of Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","volume":"2010","author":"Harsha P."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_2_23_1","unstructured":"Linial N. and Wigderson A. 2003. Expander graphs and their applications. Lecture notes of a course: http:\/\/www.math.ias.edu\/boaz\/ExpanderCourse\/. Linial N. and Wigderson A. 2003. Expander graphs and their applications. Lecture notes of a course: http:\/\/www.math.ias.edu\/boaz\/ExpanderCourse\/."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_2_25_1","unstructured":"O'Donnell R. and Guruswami V. 2005. Lecture notes from a course on the PCP theorem and hardness of approximation. O'Donnell R. and Guruswami V. 2005. Lecture notes from a course on the PCP theorem and hardness of approximation."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_10"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060647"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1236457.1236459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T04:41:34Z","timestamp":1613796094000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["10.1145\/1236457.1236459"],"URL":"http:\/\/dx.doi.org\/10.1145\/1236457.1236459","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2007,6]]}}}