{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:52Z","timestamp":1781078272298,"version":"3.54.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["Grant No. 2009054"],"award-info":[{"award-number":["Grant No. 2009054"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>We initiate the study of the trade-off between the length of a probabilistically checkable proof of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle access to the proof. Our main observation is that a verifier limited to querying a short proof cannot obtain the same soundness as that obtained by a verifier querying a long proof. Moreover, we quantify the soundness deficiency as a function of the proof-length and show that any verifier obtaining \u201cbest possible\u201d soundness must query an exponentially long proof.<\/jats:p>\n          <jats:p>\n            In terms of techniques, we focus on the special class of inspective verifiers that read at most 2 proof-bits per invocation. For such verifiers, we prove\n            <jats:italic>exponential<\/jats:italic>\n            length-soundness trade-offs that are later on used to imply our main results for the case of general (i.e., not necessarily inspective) verifiers. To prove the exponential trade-off for inspective verifiers, we show a connection between PCPP proof length and property-testing query complexity that may be of independent interest. The connection is that any linear property that can be verified with proofs of length \u2113 by linear inspective verifiers must be testable with query complexity \u2248\u2009log\u2113.\n          <\/jats:p>","DOI":"10.1145\/1595391.1595394","type":"journal-article","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T14:56:36Z","timestamp":1259592996000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Sound 3-Query PCPPs Are Long"],"prefix":"10.1145","volume":"1","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prahladh","family":"Harsha","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oded","family":"Lachish","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arie","family":"Matsliah","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), S. Arora and A. Sahai, Eds. Lecture Notes in Computer Science","volume":"2764","author":"Ben-Sasson E.","year":"1961","unstructured":"Ben-Sasson , E. , Goldreich , O. , and Sudan , M . 2003. Bounds on 2-query codeword testing . In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), S. Arora and A. Sahai, Eds. Lecture Notes in Computer Science , vol. 2764 . Springer, 216--227. doi: 10.1007\/b1 1961 . 10.1007\/b11961 Ben-Sasson, E., Goldreich, O., and Sudan, M. 2003. Bounds on 2-query codeword testing. In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), S. Arora and A. Sahai, Eds. Lecture Notes in Computer Science, vol. 2764. Springer, 216--227. doi: 10.1007\/b11961."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_56"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_2_1_11_1","unstructured":"Bogdanov A. 2005. Gap amplification fails below 1\/2. Tech. rep. TR05-046 Electronic Colloquium on Computational Complexity. http:\/\/eccc.hpi-web.de\/eccc-reports\/2005\/TR05-046\/index.html.  Bogdanov A. 2005. Gap amplification fails below 1\/2. Tech. rep. TR05-046 Electronic Colloquium on Computational Complexity. http:\/\/eccc.hpi-web.de\/eccc-reports\/2005\/TR05-046\/index.html."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132547"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225183"},{"key":"e_1_2_1_18_1","first-page":"97","article-title":"The art of uninformed decisions: A primer to property testing","volume":"75","author":"Fischer E.","year":"2001","unstructured":"Fischer , E. 2001 . The art of uninformed decisions: A primer to property testing . Bull. Eur. Assoc. Theoret. Comput. Sci. 75 , 97 -- 126 . The Computational Complexity Column. http:\/\/theorie.informatik.uni-ulm.de\/Personen\/toran\/beatcs\/. Fischer, E. 2001. The art of uninformed decisions: A primer to property testing. Bull. Eur. Assoc. Theoret. Comput. Sci. 75, 97--126. The Computational Complexity Column. http:\/\/theorie.informatik.uni-ulm.de\/Personen\/toran\/beatcs\/.","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a009"},{"key":"e_1_2_1_20_1","volume-title":"Low Density Parity Check Codes","author":"Gallager R. G.","unstructured":"Gallager , R. G. 1963. Low Density Parity Check Codes . MIT Press , Cambridge, MA . Gallager, R. G. 1963. Low Density Parity Check Codes. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 99--106","author":"Gupta A.","unstructured":"Gupta , A. and Talwar , K . 2006. Approximating unique games . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 99--106 . doi: 10.1145\/1109557.1109569. 10.1145\/1109557.1109569 Gupta, A. and Talwar, K. 2006. Approximating unique games. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 99--106. doi: 10.1145\/1109557.1109569."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC)","author":"Guruswami V.","year":"1940","unstructured":"Guruswami , V. 2006. On 2-query codeword testing with near-perfect completeness . In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC) , T. Asano, Ed. Lecture Notes in Computer Science, vol. 4288 . Springer , 267--276. doi: 10.1007\/1 1940 128_28. 10.1007\/11940128_28 Guruswami, V. 2006. On 2-query codeword testing with near-perfect completeness. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), T. Asano, Ed. Lecture Notes in Computer Science, vol. 4288. Springer, 267--276. doi: 10.1007\/11940128_28."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 18--27","author":"Guruswami V.","unstructured":"Guruswami , V. , Lewin , D. , Sudan , M. , and Trevisan , L . 1998. A tight characterization of NP with 3-query PCPs . In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 18--27 . doi: 10.1109\/SFCS.1998.743424. 10.1109\/SFCS.1998.743424 Guruswami, V., Lewin, D., Sudan, M., and Trevisan, L. 1998. A tight characterization of NP with 3-query PCPs. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 18--27. doi: 10.1109\/SFCS.1998.743424."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_26"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001606"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_2_1_37_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. http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-026\/index.html.  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. http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-026\/index.html."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/060656838"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.60"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132519"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 26th International Colloquium of Automata, Languages and Programming (ICALP)","author":"Szegedy M.","unstructured":"Szegedy , M. 1999. Many-valued logics and holographic proofs . In Proceedings of the 26th International Colloquium of Automata, Languages and Programming (ICALP) , J. Wiedermann, P. van Emde Boas, and M. Nien, Eds. Lecture Notes in Computer Science, vol. 1644 . Springer , 676--686. doi: 10.1007\/3-540-48523-6. 10.1007\/3-540-48523-6 Szegedy, M. 1999. Many-valued logics and holographic proofs. In Proceedings of the 26th International Colloquium of Automata, Languages and Programming (ICALP), J. Wiedermann, P. van Emde Boas, and M. Nien, Eds. Lecture Notes in Computer Science, vol. 1644. Springer, 676--686. doi: 10.1007\/3-540-48523-6."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.22"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_46"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 201--210","author":"Zwick U.","year":"1998","unstructured":"Zwick , U. 1998 . Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 201--210 . doi:10.1145\/314613.314701. 10.1145\/314613.314701 Zwick, U. 1998. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 201--210. doi:10.1145\/314613.314701."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595391.1595394","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1595391.1595394","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:03Z","timestamp":1750253403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595391.1595394"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1595391.1595394"],"URL":"https:\/\/doi.org\/10.1145\/1595391.1595394","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2008-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}