{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T16:04:11Z","timestamp":1780934651289,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,11,8]],"date-time":"2017-11-08T00:00:00Z","timestamp":1510099200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Community's Seventh Framework Programme","award":["240258"],"award-info":[{"award-number":["240258"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF CCF-1253886, NSF CCF-1540634 and CCF-0832797"],"award-info":[{"award-number":["NSF CCF-1253886, NSF CCF-1540634 and CCF-0832797"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sloan Fellowship"},{"name":"US-Israel Binational Science Foundation","award":["2014359"],"award-info":[{"award-number":["2014359"]}]},{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["1501\/14"],"award-info":[{"award-number":["1501\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Tubitak","award":["111T234"],"award-info":[{"award-number":["111T234"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,11,8]]},"abstract":"<jats:p>\n                    The PCP theorem [Arora et al. 1998; Arora and Safra 1998] says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, that is, how long is the PCP compared to the original NP-proof? The state-of-the-art work of Ben-Sasson and Sudan [2008] and Dinur [2007] shows that one can encode proofs of length\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    by PCPs of length\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    \u00b7 poly log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>\u03b5<\/jats:sup>\n                    , then one can construct PCPs of length\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) for circuit-SAT, and PCPs of length\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    log\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    ) for any language in NTIME(\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    ).\n                  <\/jats:p>\n                  <jats:p>\n                    More specifically, for any \u03b5 &gt; 0, we present (nonuniform) probabilistically checkable proofs (PCPs) of length 2\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">O<\/jats:italic>\n                      (1\/\u03b5)\n                    <\/jats:sup>\n                    \u00b7\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    that can be checked using\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>\u03b5<\/jats:sup>\n                    queries for circuit-SAT instances of size\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    . Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity (\n                    <jats:italic toggle=\"yes\">o<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    )).\n                  <\/jats:p>\n                  <jats:p>Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations that are crucial in earlier high-rate algebraic PCP constructions. Using this observation, we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed in the appendix to this article for the first time for every message length, building on an earlier construction for infinitely many message lengths by Stichtenoth [2006].<\/jats:p>","DOI":"10.1145\/2901294","type":"journal-article","created":{"date-parts":[[2016,11,9]],"date-time":"2016-11-09T08:36:49Z","timestamp":1478680609000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity"],"prefix":"10.1145","volume":"63","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yohay","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Swastik","family":"Kopparty","sequence":"additional","affiliation":[{"name":"Rutgers, Brunswick, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[{"name":"Haifa University, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Henning","family":"Stichtenoth","sequence":"additional","affiliation":[{"name":"Sabanci University, Istanbul, Turkey"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,11,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/971651.971653"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Congress of Mathematicians (ICM\u201902)","volume":"3","author":"Arora Sanjeev","year":"2002","unstructured":"Sanjeev Arora. 2002. How NP got a new definition: A survey of probabilistically checkable proofs. In Proceedings of the International Congress of Mathematicians (ICM\u201902), Vol. 3. 637--648."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Babai Lance Fortnow Leonid A. Levin and Mario Szegedy. 1991. Checking computations in polylogarithmic time. In STOC. 21--31. 10.1145\/103418.103428","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422481"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488681"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Eli Ben-Sasson Ariel Gabizon Yohay Kaplan Swastik Kopparty and Shubhangi Saraf. 2013. A new family of locally correctable codes based on degree-lifted algebraic geometry codes. In STOC. 10.1145\/2488608.2488714","DOI":"10.1145\/2488608.2488714"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.27"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v28:4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Eli Ben-Sasson and Michael Viderman. 2009a. Composition of Semi-LTCs by Two-Wise Tensor Products. In APPROX-RANDOM. 378--391. 10.1007\/978-3-642-03685-9_29","DOI":"10.1007\/978-3-642-03685-9_29"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a012"},{"key":"e_1_2_1_16_1","volume-title":"Combinatorics: Topics, Techniques, Algorithms","author":"Cameron Peter J.","year":"1998","unstructured":"Peter J. Cameron. 1998. Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge, MA."},{"key":"e_1_2_1_17_1","volume-title":"On the robust testability of tensor products of codes. Electronic Colloquium on Computational Complexity (ECCC) 104","author":"Coppersmith Don","year":"2005","unstructured":"Don Coppersmith and Atri Rudra. 2005. On the robust testability of tensor products of codes. Electronic Colloquium on Computational Complexity (ECCC) 104 (2005)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0013-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Irit Dinur Madhu Sudan and Avi Wigderson. 2006. Robust local testability of tensor products of LDPC codes. In APPROX-RANDOM. 304--315. 10.1007\/11830924_29","DOI":"10.1007\/11830924_29"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.1996.0147"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01170848"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2028116.2028142"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.01.007"},{"key":"e_1_2_1_27_1","volume-title":"Retrieved","author":"Guruswami Venkatesan","year":"2005","unstructured":"Venkatesan Guruswami and Ryan O\u2019Donnell. 2005. The PCP Theorem and Hardness of Approximation. Retrieved August 12, 2016 from http:\/\/www.cs.washington.edu\/education\/courses\/533\/05au\/."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001606"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"B. Huppert. 1967. Endliche Gruppen I Springer-Verlag Grundlehren der mathematischen Wissenschaften No. 134.","DOI":"10.1007\/978-3-642-64981-3"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056879"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374434"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Swastik Kopparty Shubhangi Saraf and Sergey Yekhanin. 2011. High-rate codes with sublinear-time decoding. In STOC. 167--176. 10.1145\/1993636.1993660","DOI":"10.1145\/1993636.1993660"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2758-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/119339"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_36_1","volume-title":"The Theory of Error Correcting Codes","author":"MacWilliams Florence Jessie","unstructured":"Florence Jessie MacWilliams and Neil James Alexander Sloane. 1988. The Theory of Error Correcting Codes. Elsevier\/North-Holland, Amsterdam."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.14"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.11.007"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/110829660"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9169-y"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2179519"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322138"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.945244"},{"key":"e_1_2_1_45_1","volume-title":"Algebraic Function Fields and Codes","author":"Stichtenoth Henning","unstructured":"Henning Stichtenoth. 1993. Algebraic Function Fields and Codes. Springer. I--X, 1--260 pages."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.872986"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1524143"},{"key":"e_1_2_1_48_1","unstructured":"Madhu Sudan. 2001. Algorithmic introduction to coding theory (Lecture notes)."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1980617.1980631"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19821090103"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","unstructured":"M. A. Tsfasman and S. G. Vl\u0103du\u0163. 1991. Algebraic-Geometric Codes Kluwer.","DOI":"10.5555\/574322"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","unstructured":"Paul Valiant. 2005. The tensor product of two codes is not necessarily robustly testable. In APPROX-RANDOM. 472--481. 10.1007\/11538462_40","DOI":"10.1007\/11538462_40"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Michael Viderman. 2012. A combination of testability and decodability by tensor products. In APPROX-RANDOM. 651--662.","DOI":"10.1007\/978-3-642-32512-0_55"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/575571"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2901294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2901294","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2901294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:36:52Z","timestamp":1763458612000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2901294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,8]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,8]]}},"alternative-id":["10.1145\/2901294"],"URL":"https:\/\/doi.org\/10.1145\/2901294","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,8]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}