{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:00:53Z","timestamp":1778292053607,"version":"3.51.4"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["1262\/18 and 2137\/19"],"award-info":[{"award-number":["1262\/18 and 2137\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Technion Hiroshi Fujiwara cyber security research center and Israel cyber directorate"},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["ERC, FASTPROOF, 101041208"],"award-info":[{"award-number":["ERC, FASTPROOF, 101041208"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP, the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP). Efficient IOPs are currently at the core of leading practical implementations of highly efficient proof-systems.<\/jats:p>\n          <jats:p>\n            In this work we construct, for a large class of NP relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any NP relation for which membership can be decided in polynomial-time with bounded polynomial space (i.e., space\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03be<\/jats:sup>\n            for some sufficiently small constant \u03be &gt; 0; e.g., SAT, Hamiltonicity, Clique, Vertex-Cover) and for any constant \u03b3 &gt; 0, we construct an IOP with communication complexity (1 + \u03b3) \u22c5\n            <jats:italic>n<\/jats:italic>\n            , where\n            <jats:italic>n<\/jats:italic>\n            is the original witness length. The number of rounds, as well as the number of queries made by the IOP verifier, are constant.\n          <\/jats:p>\n          <jats:p>\n            This result improves over prior works on short IOPs\/PCPs in two ways. First, the communication complexity in these short IOPs is proportional to the complexity of\n            <jats:italic>verifying<\/jats:italic>\n            the NP witness, which can be polynomially larger than the witness size. Second, even ignoring the difference between witness length and non-deterministic verification time, prior works incur (at the very least) a large constant multiplicative overhead to the communication complexity.\n          <\/jats:p>\n          <jats:p>\n            In particular, as a special case, we also obtain an IOP for CircuitSAT with communication complexity (1 + \u03b3) \u22c5\n            <jats:italic>t<\/jats:italic>\n            , for circuits of size\n            <jats:italic>t<\/jats:italic>\n            and any constant \u03b3 &gt; 0. This improves upon the prior state-of-the-art work of Ben\u00a0Sasson\u00a0et al.\u00a0(ICALP, 2017) who construct an IOP for CircuitSAT with communication length\n            <jats:italic>c \u22c5 t<\/jats:italic>\n            for a large (unspecified) constant\n            <jats:italic>c<\/jats:italic>\n            \u2265 1.\n          <\/jats:p>\n          <jats:p>\n            Our proof leverages the local testability and (relaxed) local correctability of high-rate tensor codes, as well as their support of a sumcheck-like procedure. In particular, we bypass the barrier imposed by the low rate of\n            <jats:italic>multiplication codes<\/jats:italic>\n            (e.g., Reed\u2013Solomon, Reed\u2013Muller, or AG codes)\u2014a key building block of all known short PCP\/IOP constructions.\n          <\/jats:p>","DOI":"10.1145\/3661483","type":"journal-article","created":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T11:13:03Z","timestamp":1714043583000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Local Proofs Approaching the Witness Length"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8416-893X","authenticated-orcid":false,"given":"Noga","family":"Ron-Zewi","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Haifa, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5481-7276","authenticated-orcid":false,"given":"Ron","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Computer Science, Technion Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_4_2_2","first-page":"25","volume-title":"Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Abboud Amir","year":"2017","unstructured":"Amir Abboud, Aviad Rubinstein, and Ryan Williams. 2017. Distributed PCP theorems for hardness of approximation in P. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 25\u201336. DOI:10.1109\/FOCS.2017.12"},{"key":"e_1_3_4_3_2","first-page":"836","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Applebaum Benny","year":"2017","unstructured":"Benny Applebaum. 2017. Exponentially-hard Gap-CSP and local PRG via local hardcore functions. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 836\u2013847. DOI:10.1109\/FOCS.2017.82"},{"key":"e_1_3_4_4_2","first-page":"24:1\u201324:16","volume-title":"Proceedings of the 37th Computational Complexity Conference (CCC)","author":"Arnon Gal","year":"2022","unstructured":"Gal Arnon, Alessandro Chiesa, and Eylon Yogev. 2022. Hardness of approximation for stochastic problems via interactive oracle proofs. In Proceedings of the 37th Computational Complexity Conference (CCC). LIPIcs, Vol. 234, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 24:1\u201324:16. DOI:10.4230\/LIPIcs.CCC.2022.24"},{"key":"e_1_3_4_5_2","first-page":"64","volume-title":"Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)","volume":"13276","author":"Arnon Gal","year":"2022","unstructured":"Gal Arnon, Alessandro Chiesa, and Eylon Yogev. 2022. A PCP theorem for interactive proofs and applications. In Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Vol. 13276, Springer, 64\u201394. DOI:10.1007\/978-3-031-07085-3_3"},{"issue":"3","key":"e_1_3_4_6_2","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","article-title":"Proof verification and intractability of approximation problems","volume":"45","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. 1998. Proof verification and intractability of approximation problems. Journal of the ACM 45, 3 (1998), 501\u2013555.","journal-title":"Journal of the ACM"},{"issue":"1","key":"e_1_3_4_7_2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","article-title":"Probabilistic checkable proofs: A new characterization of NP","volume":"45","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora and Shmuel Safra. 1998. Probabilistic checkable proofs: A new characterization of NP. Journal of the ACM 45, 1 (1998), 70\u2013122.","journal-title":"Journal of the ACM"},{"key":"e_1_3_4_8_2","first-page":"21","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC)","author":"Babai L\u00e1szl\u00f3","year":"1991","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy. 1991. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC). ACM, 21\u201331. DOI:10.1145\/103418.103428"},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","article-title":"Non-deterministic exponential time has two-prover interactive protocols","volume":"1","author":"Babai L\u00e1szl\u00f3","year":"1991","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, and Carsten Lund. 1991. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1 (1991), 3\u201340.","journal-title":"Computational Complexity"},{"key":"e_1_3_4_10_2","series-title":"LIPIcs","first-page":"9:1\u20139:27","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"151","author":"Ben-Eliezer Omri","year":"2020","unstructured":"Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. 2020. Hard properties with (very) short PCPPs and their applications. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, Vol. 151, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 9:1\u20139:27. DOI:10.4230\/LIPIcs.ITCS.2020.9"},{"key":"e_1_3_4_11_2","first-page":"14:1\u201314:17","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Ben-Sasson Eli","year":"2018","unstructured":"Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018. Fast Reed-Solomon interactive oracle proofs of proximity. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 14:1\u201314:17. DOI:10.4230\/LIPIcs.ICALP.2018.14"},{"key":"e_1_3_4_12_2","first-page":"701","volume-title":"Proceedings of the 39th Annual International Cryptology Conference (Crypto)","author":"Ben-Sasson Eli","year":"2019","unstructured":"Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2019. Scalable zero knowledge with no trusted setup. In Proceedings of the 39th Annual International Cryptology Conference (Crypto). Lecture Notes in Computer Science, Springer, 701\u2013732. DOI:10.1007\/978-3-030-26954-8_23"},{"key":"e_1_3_4_13_2","first-page":"40:1\u201340:15","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Ben-Sasson Eli","year":"2017","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. 2017. Interactive oracle proofs with constant rate and query complexity. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 40:1\u201340:15. DOI:10.4230\/LIPIcs.ICALP.2017.40"},{"key":"e_1_3_4_14_2","first-page":"585","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC)","author":"Ben-Sasson Eli","year":"2013","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. 2013. On the concrete efficiency of probabilistically-checkable proofs. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC). ACM, 585\u2013594. DOI:10.1145\/2488608.2488681"},{"key":"e_1_3_4_15_2","first-page":"103","volume-title":"Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)","author":"Ben-Sasson Eli","year":"2019","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. 2019. Aurora: Transparent succinct arguments for R1CS. In Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science, Springer, 103\u2013128. DOI:10.1007\/978-3-030-17653-2_4"},{"key":"e_1_3_4_16_2","first-page":"31","volume-title":"Proceedings of the 14th IACR Theory of Cryptography Conference (TCC)","author":"Ben-Sasson Eli","year":"2016","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. 2016. Interactive oracle proofs. In Proceedings of the 14th IACR Theory of Cryptography Conference (TCC). Springer, 31\u201360. DOI:10.1007\/978-3-662-53644-5_2"},{"key":"e_1_3_4_17_2","series-title":"LIPIcs","first-page":"5:1\u20135:32","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"151","author":"Ben-Sasson Eli","year":"2020","unstructured":"Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. 2020. DEEP-FRI: Sampling outside the box improves soundness. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, Vol. 151, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 5:1\u20135:32. DOI:10.4230\/LIPIcs.ITCS.2020.5"},{"issue":"4","key":"e_1_3_4_18_2","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/S0097539705446810","article-title":"Robust PCPs of proximity, shorter PCPs, and applications to coding","volume":"36","author":"Ben-Sasson Eli","year":"2006","unstructured":"Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. 2006. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM Journal on Computing 36, 4 (2006), 889\u2013974.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2901294"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20120"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0074-8"},{"key":"e_1_3_4_23_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-030-64378-2_2","volume-title":"Proceedings of the 18th International Theory of Cryptography Conference (TCC)","volume":"12551","author":"Bootle Jonathan","year":"2020","unstructured":"Jonathan Bootle, Alessandro Chiesa, and Jens Groth. 2020. Linear-time arguments with sublinear verification from tensor codes. In Proceedings of the 18th International Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science, Vol. 12551, Springer, 19\u201346. DOI:10.1007\/978-3-030-64378-2_2"},{"key":"e_1_3_4_24_2","first-page":"275","volume-title":"Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)","author":"Bootle Jonathan","year":"2022","unstructured":"Jonathan Bootle, Alessandro Chiesa, and Siqi Liu. 2022. Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier. In Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Lecture Notes in Computer Science, Vol. 13276, Springer, 275\u2013304. DOI:10.1007\/978-3-031-07085-3_10"},{"key":"e_1_3_4_25_2","first-page":"1","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chen Lijie","year":"2019","unstructured":"Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy Rothblum, and Aviad Rubinstein. 2019. Fine-grained complexity meets IP = PSPACE. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1\u201320."},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_4_27_2","first-page":"128","article-title":"Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover","volume":"23","author":"Dinur Irit","year":"2016","unstructured":"Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC) 23 (2016), 128. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2016\/128","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_4_28_2","first-page":"357","volume-title":"Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC)","author":"Dinur Irit","year":"2022","unstructured":"Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. 2022. Locally testable codes with constant rate, distance, and locality. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). ACM, 357\u2013374. DOI:10.1145\/3519935.3520024"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_3_4_30_2","first-page":"304","volume-title":"Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM)","author":"Dinur Irit","year":"2006","unstructured":"Irit Dinur, Madhu Sudan, and Avi Wigderson. 2006. Robust local testability of tensor products of LDPC codes. In Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM). Springer, 304\u2013315."},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.005"},{"issue":"2","key":"e_1_3_4_32_2","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","article-title":"Interactive proofs and the hardness of approximating cliques","volume":"43","author":"Feige Uriel","year":"1996","unstructured":"Uriel Feige, Shafi Goldwasser, L\u00e1szl\u00f3 Lov\u00e1sz, Shmuel Safra, and Mario Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. Journal of the ACM 43, 2 (1996), 268\u2013292.","journal-title":"Journal of the ACM"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000084"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00116-1"},{"issue":"8","key":"e_1_3_4_37_2","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/j.ipl.2012.01.007","article-title":"The tensor product of two good codes is not necessarily locally testable","volume":"112","author":"Goldreich Oded","year":"2012","unstructured":"Oded Goldreich and Or Meir. 2012. The tensor product of two good codes is not necessarily locally testable. Information Processing Letters 112, 8\u20139 (2012), 351\u2013355.","journal-title":"Information Processing Letters"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-002-0169-0"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_4_40_2","article-title":"Brakedown: Linear-Time and Post-Quantum SNARKs for R1CS","author":"Golovnev Alexander","year":"2021","unstructured":"Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad Wahby. 2021. Brakedown: Linear-Time and Post-Quantum SNARKs for R1CS. Cryptology ePrint Archive, Report 2021\/1043. Retrieved from https:\/\/ia.cr\/2021\/1043","journal-title":"Cryptology ePrint Archive, Report 2021\/1043"},{"key":"e_1_3_4_41_2","series-title":"LIPIcs","first-page":"27:1\u201327:11","volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"94","author":"Gur Tom","year":"2018","unstructured":"Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. 2018. Relaxed locally correctable codes. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, Vol. 94, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 27:1\u201327:11. Retrieved from http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-060-6"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0136-9"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054893"},{"key":"e_1_3_4_46_2","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1007\/978-3-540-70583-3_44","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Kalai Yael Tauman","year":"2008","unstructured":"Yael Tauman Kalai and Ran Raz. 2008. Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 536\u2013547. DOI:10.1007\/978-3-540-70583-3_44"},{"key":"e_1_3_4_47_2","first-page":"422","volume-title":"Proceedings of the 35th Annual International Cryptology Conference (Crypto)","author":"Kalai Yael Tauman","year":"2015","unstructured":"Yael Tauman Kalai and Ron D. Rothblum. 2015. Arguments of proximity. In Proceedings of the 35th Annual International Cryptology Conference (Crypto). Lecture Notes in Computer Science, Springer, 422\u2013442. DOI:10.1007\/978-3-662-48000-7_21"},{"key":"e_1_3_4_48_2","first-page":"85","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","year":"1975","unstructured":"R. M. Karp. 1975. Reducibility among combinatorial problems. In Complexity of Computer Computations, Raymond E. Miller and James W. Thatcher (Eds.). Plenum Press, 85\u2013103."},{"key":"e_1_3_4_49_2","first-page":"723","volume-title":"Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC)","author":"Kilian Joe","year":"1992","unstructured":"Joe Kilian. 1992. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC). ACM, 723\u2013732. DOI:10.1145\/129712.129782"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3051093"},{"issue":"5","key":"e_1_3_4_51_2","first-page":"28","article-title":"High-rate codes with sublinear-time decoding","volume":"61","author":"Kopparty Swastik","year":"2014","unstructured":"Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. 2014. High-rate codes with sublinear-time decoding. Journal of the ACM 61, 5 (2014), 28.","journal-title":"Journal of the ACM"},{"issue":"4","key":"e_1_3_4_52_2","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","article-title":"Algebraic methods for interactive proof systems","volume":"39","author":"Lund Carsten","year":"1992","unstructured":"Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. 1992. Algebraic methods for interactive proof systems. Journal of the ACM 39, 4 (1992), 859\u2013868.","journal-title":"Journal of the ACM"},{"key":"e_1_3_4_53_2","series-title":"LIPIcs","first-page":"78:1\u201378:15","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"80","author":"Manurangsi Pasin","year":"2017","unstructured":"Pasin Manurangsi and Prasad Raghavendra. 2017. A birthday repetition theorem and complexity of approximating dense CSPs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs, Vol. 80, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 78:1\u201378:15. Retrieved from http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-041-5"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1137\/110829660"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-014-0080-5"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"issue":"3","key":"e_1_3_4_57_2","first-page":"313","article-title":"Short PCPPs verifiable in polylogarithmic time with O (1) queries","volume":"56","author":"Mie Thilo","year":"2009","unstructured":"Thilo Mie. 2009. Short PCPPs verifiable in polylogarithmic time with O (1) queries. Annals of Mathematics and Artificial Intelligence 56, 3\u20134 (2009), 313\u2013338.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"3","key":"e_1_3_4_58_2","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1109\/IREPGELC.1954.6499441","article-title":"Application of boolean algebra to switching circuit design and to error detection","volume":"3","author":"Muller David","year":"1954","unstructured":"David Muller. 1954. Application of boolean algebra to switching circuit design and to error detection. Transactions of the IRE Professional Group on Electronic Computers 3, 3 (1954), 6\u201312.","journal-title":"Transactions of the IRE Professional Group on Electronic Computers"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","unstructured":"Shafik Nassar and Ron D. Rothblum. 2022. Succinct interactive oracle proofs: Applications and limitations. Advances in Cryptology - CRYPTO 2022-42nd Annual International Cryptology Conference CRYPTO 2022 Lecture Notes in Computer Science Yevgeniy Dodis and Thomas Shrimpton (Eds.). Vol. 13507 Springer 504\u2013532. DOI:10.1007\/978-3-031-15802-5_18","DOI":"10.1007\/978-3-031-15802-5_18"},{"key":"e_1_3_4_60_2","first-page":"375","volume-title":"Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC)","author":"Panteleev Pavel","year":"2022","unstructured":"Pavel Panteleev and Gleb Kalachev. 2022. Asymptotically good quantum and locally testable classical LDPC codes. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). ACM, 375\u2013388. DOI:10.1145\/3519935.3520017"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322138"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2281145"},{"key":"e_1_3_4_63_2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/TIT.1954.1057465","article-title":"A class of multiple-error-correcting codes and the decoding scheme","volume":"4","author":"Reed Irving","year":"1954","unstructured":"Irving Reed. 1954. A class of multiple-error-correcting codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory 4 (1954), 38\u201349.","journal-title":"Transactions of the IRE Professional Group on Information Theory"},{"issue":"2","key":"e_1_3_4_64_2","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0108018","article-title":"Polynomial codes over certain finite fields","volume":"8","author":"Reed Irving S.","year":"1960","unstructured":"Irving S. Reed and Gustave Solomon. 1960. Polynomial codes over certain finite fields. SIAM Journal of the Society for Industrial and Applied Mathematics 8, 2 (1960), 300\u2013304.","journal-title":"SIAM Journal of the Society for Industrial and Applied Mathematics"},{"key":"e_1_3_4_65_2","unstructured":"Omer Reingold Guy N. Rothblum and Ron D. Rothblum. 2017. Personal Communication."},{"key":"e_1_3_4_66_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096773"},{"key":"e_1_3_4_67_2","first-page":"127","article-title":"Local proofs approaching the witness length","author":"Ron-Zewi Noga","year":"2019","unstructured":"Noga Ron-Zewi and Ron Rothblum. 2019. Local proofs approaching the witness length. Electronic Colloquium on Computational Complexity (2019), 127. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2019\/127https:\/\/eccc.weizmann.ac.il\/report\/2019\/127\/","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_3_4_68_2","first-page":"1353","volume-title":"Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC)","author":"Ron-Zewi Noga","year":"2022","unstructured":"Noga Ron-Zewi and Ron Rothblum. 2022. Proving as fast as computing: Succinct arguments with constant prover overhead. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). ACM, 1353\u20131363."},{"key":"e_1_3_4_69_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-3-030-64378-2_5","volume-title":"Proceedings of the 18th IACR Theory of Cryptography Conference (TCC)","volume":"12551","author":"Rothblum Guy N.","year":"2020","unstructured":"Guy N. Rothblum and Ron D. Rothblum. 2020. Batch verification and proofs of proximity with polylog overhead. In Proceedings of the 18th IACR Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science, Vol. 12551, Springer, 108\u2013138. DOI:10.1007\/978-3-030-64378-2_5"},{"key":"e_1_3_4_70_2","first-page":"793","volume-title":"Proceedings of the 45th Annual Symposium on Theory of Computing (STOC)","author":"Rothblum Guy N.","year":"2013","unstructured":"Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. 2013. Interactive proofs of proximity: Delegating computation in sublinear time. In Proceedings of the 45th Annual Symposium on Theory of Computing (STOC). ACM, 793\u2013802. DOI:10.1145\/2488608.2488709"},{"key":"e_1_3_4_71_2","first-page":"1260","volume-title":"Proceedings of the 50th Annual Symposium on Theory of Computing (STOC)","author":"Rubinstein Aviad","year":"2018","unstructured":"Aviad Rubinstein. 2018. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual Symposium on Theory of Computing (STOC). ACM, 1260\u20131268. DOI:10.1145\/3188745.3188916"},{"key":"e_1_3_4_72_2","first-page":"283","volume-title":"Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Shoup Victor","year":"1988","unstructured":"Victor Shoup. 1988. New algorithms for finding irreducible polynomials over finite fields. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 283\u2013290. DOI:10.1109\/SFCS.1988.21944"},{"issue":"6","key":"e_1_3_4_73_2","doi-asserted-by":"crossref","first-page":"1723","DOI":"10.1109\/18.556668","article-title":"Linear-time encodable and decodable error-correcting codes","volume":"42","author":"Spielman Daniel A.","year":"1996","unstructured":"Daniel A. Spielman. 1996. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory 42, 6 (1996), 1723\u20131731.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"e_1_3_4_74_2","doi-asserted-by":"crossref","first-page":"2218","DOI":"10.1109\/TIT.2006.872986","article-title":"Transitive and self-dual codes attaining the Tsfasman-Vladut-Zink bound","volume":"52","author":"Stichtenoth Henning","year":"2006","unstructured":"Henning Stichtenoth. 2006. Transitive and self-dual codes attaining the Tsfasman-Vladut-Zink bound. IEEE Transactions on Information Theory 52, 5 (2006), 2218\u20132224.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_4_75_2","unstructured":"Madhu Sudan. 2000. Probabilistically Checkable Proofs - Lecture Notes. Retrieved May 9 2024 from http:\/\/madhu.seas.harvard.edu\/MIT\/pcp\/pcp.ps"},{"key":"e_1_3_4_76_2","unstructured":"Madhu Sudan. 2001. Algorithmic Introduction to Coding Theory (Lecture Notes)."},{"key":"e_1_3_4_77_2","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepcs\u00e9nyi R\u00f3bert","year":"1987","unstructured":"R\u00f3bert Szelepcs\u00e9nyi. 1987. The method of forcing for nondeterministic automata. Bulletin of the EATCS 33 (1987), 96\u201399.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_4_78_2","first-page":"472","volume-title":"Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM)","author":"Valiant Paul","year":"2005","unstructured":"Paul Valiant. 2005. The tensor product of two codes is not necessarily robustly testable. In Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM). Springer, 472\u2013481."},{"issue":"3","key":"e_1_3_4_79_2","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1002\/rsa.20498","article-title":"A combination of testability and decodability by tensor products","volume":"46","author":"Viderman Michael","year":"2015","unstructured":"Michael Viderman. 2015. A combination of testability and decodability by tensor products. Random Structures and Algorithms 46, 3 (2015), 572\u2013598.","journal-title":"Random Structures and Algorithms"},{"key":"e_1_3_4_80_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/978-3-031-15985-5_11","volume-title":"Advances in Cryptology - CRYPTO 2022-42nd Annual International Cryptology Conference, CRYPTO 2022","volume":"13510","author":"Xie Tiancheng","year":"2022","unstructured":"Tiancheng Xie, Yupeng Zhang, and Dawn Song. 2022. Orion: Zero knowledge proof with linear prover time. In Advances in Cryptology - CRYPTO 2022-42nd Annual International Cryptology Conference, CRYPTO 2022, Lecture Notes in Computer Science, Vol. 13510, Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, 299\u2013328. DOI:10.1007\/978-3-031-15985-5_11"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661483","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3661483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:31Z","timestamp":1750294711000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,11]]},"references-count":79,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3661483"],"URL":"https:\/\/doi.org\/10.1145\/3661483","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,11]]},"assertion":[{"value":"2022-10-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-16","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}