{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:00:27Z","timestamp":1781078427231,"version":"3.54.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,6,25]],"date-time":"2008-06-25T00:00:00Z","timestamp":1214352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>\n            We show that the NP-Complete language 3Sat has a PCP verifier that makes two queries to a proof of almost-linear size and achieves subconstant probability of error \u03b5=\n            <jats:italic>o<\/jats:italic>\n            (1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query. The number of bits representing a symbol in the proof depends only on the error \u03b5. Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small)\n            <jats:italic>constant<\/jats:italic>\n            error and\n            <jats:italic>polynomial<\/jats:italic>\n            size. There were also PCP Theorems with\n            <jats:italic>subconstant<\/jats:italic>\n            error and\n            <jats:italic>almost-linear<\/jats:italic>\n            size, but a constant number of queries that is\n            <jats:italic>larger<\/jats:italic>\n            than 2.\n          <\/jats:p>\n          <jats:p>As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following:<\/jats:p>\n          <jats:p>\n            (1) 3Sat cannot be efficiently approximated to within a factor of 7\/8+\n            <jats:italic>o<\/jats:italic>\n            (1), unless P=NP. This holds even under almost-linear reductions. Previously, the best known NP-hardness factor was 7\/8+\u03b5 for any constant \u03b5&gt;0, under polynomial reductions (H\u00e5stad).\n          <\/jats:p>\n          <jats:p>\n            (2) 3Lin cannot be efficiently approximated to within a factor of 1\/2+\n            <jats:italic>o<\/jats:italic>\n            (1), unless P=NP. This holds even under almost-linear reductions. Previously, the best known NP-hardness factor was 1\/2+\u03b5 for any constant \u03b5&gt;0, under polynomial reductions (H\u00e5stad).\n          <\/jats:p>\n          <jats:p>\n            (3) A PCP Theorem with amortized query complexity 1 +\n            <jats:italic>o<\/jats:italic>\n            (1) and amortized free bit complexity\n            <jats:italic>o<\/jats:italic>\n            (1). Previously, the best-known amortized query complexity and free bit complexity were 1+\u03b5 and \u03b5, respectively, for any constant \u03b5&gt;0 (Samorodnitsky and Trevisan).\n          <\/jats:p>\n          <jats:p>\n            One of the new ideas that we use is a new technique for doing the\n            <jats:italic>composition<\/jats:italic>\n            step in the (classical) proof of the PCP Theorem, without increasing the number of queries to the proof. We formalize this as a composition of new objects that we call\n            <jats:italic>Locally Decode\/Reject Codes<\/jats:italic>\n            (LDRC). The notion of LDRC was implicit in several previous works, and we make it explicit in this work. We believe that the formulation of LDRCs and their construction are of independent interest.\n          <\/jats:p>","DOI":"10.1145\/1754399.1754402","type":"journal-article","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T17:43:38Z","timestamp":1277487818000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":72,"title":["Two-query PCP with subconstant error"],"prefix":"10.1145","volume":"57","author":[{"given":"Dana","family":"Moshkovitz","sequence":"first","affiliation":[{"name":"The Institute for Advanced Study, Princeton, New Jersey"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[{"name":"Weizmann Institute, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,6,25]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"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.1137\/S0097539796302531"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412713"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301265"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536422"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225183"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250852"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067318"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_2_27_1","unstructured":"Moshkovitz D. and Raz R. 2007. Sub-constant error probabilistically checkable proof of almost-linear size. Tech. rep. TR07-026 Electronic Colloquium on Computational Complexity.  Moshkovitz D. and Raz R. 2007. Sub-constant error probabilistically checkable proof of almost-linear size. Tech. rep. TR07-026 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/060656838"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374378"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_2_2_35_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP'07)","author":"Szegedy M."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1754399.1754402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1754399.1754402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:50Z","timestamp":1750245770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1754399.1754402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,25]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1754399.1754402"],"URL":"https:\/\/doi.org\/10.1145\/1754399.1754402","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6,25]]},"assertion":[{"value":"2009-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}