{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:19Z","timestamp":1781078239870,"version":"3.54.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T00:00:00Z","timestamp":1696982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ERC Project NTSC","award":["742754"],"award-info":[{"award-number":["742754"]}]},{"name":"NSF-BSF","award":["2015782"],"award-info":[{"award-number":["2015782"]}]},{"name":"BSF","award":["2018393, 2014359"],"award-info":[{"award-number":["2018393, 2014359"]}]},{"name":"Ministry of Science and Technology, Israel and Department of Science and Technology, Government of India"},{"name":"NSF","award":["CCF-1540634 and CCF-1814409"],"award-info":[{"award-number":["CCF-1540634 and CCF-1814409"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            A collection of sets displays a\n            <jats:italic>proximity gap<\/jats:italic>\n            with respect to some property if for every set in the collection, either (i) all members are \u03b4-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are \u03b4-close to the property. In particular, no set in the collection has roughly half of its members \u03b4-close to the property and the others \u03b4-far from it.\n          <\/jats:p>\n          <jats:p>\n            We show that the collection of affine spaces displays a proximity gap with respect to Reed\u2013Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any \u03b4 smaller than the Johnson\/Guruswami\u2013Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least)\n            <jats:italic>linear<\/jats:italic>\n            size in the RS code dimension, for \u03b4 smaller than the unique decoding radius. Concretely, if \u03b4 is smaller than half the minimal distance of an RS code\n            <jats:italic>V<\/jats:italic>\n            \u2282 \ud835\udd3d\n            <jats:italic>\n              <jats:sub>q<\/jats:sub>\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            , then every affine space is either entirely \u03b4-close to the code or, alternatively, at most an (\n            <jats:italic>n\/q<\/jats:italic>\n            )-fraction of it is \u03b4-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems.\n          <\/jats:p>\n          <jats:p>\n            We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed\u2013Solomon codes (due to Berlekamp\u2013Welch and Guruswami\u2013Sudan) on a\n            <jats:italic>formal element<\/jats:italic>\n            of an affine space. This involves working with Reed\u2013Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.\n          <\/jats:p>","DOI":"10.1145\/3614423","type":"journal-article","created":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T09:24:23Z","timestamp":1692091463000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Proximity Gaps for Reed\u2013Solomon Codes"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0708-0483","authenticated-orcid":false,"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"StarkWare Industries Ltd., Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9952-5947","authenticated-orcid":false,"given":"Dan","family":"Carmon","sequence":"additional","affiliation":[{"name":"StarkWare Industries Ltd., Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4096-6305","authenticated-orcid":false,"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2704-8808","authenticated-orcid":false,"given":"Swastik","family":"Kopparty","sequence":"additional","affiliation":[{"name":"Departments of Mathematics and of Computer Science, University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0874-2978","authenticated-orcid":false,"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Departments of Mathematics and of Computer Science, University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,10,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134104"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"e_1_3_3_4_2","unstructured":"Olivier B\u00e9gassat. 2019. Bivariate Polynomial Divisibility Test of Spielman. Retrieved from https:\/\/mathoverflow.net\/questions\/348657\/bivariate-polynomial-divisibility-test-of-spielman"},{"key":"e_1_3_3_5_2","first-page":"1","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC\u201988)","author":"Ben-Or Michael","year":"1988","unstructured":"Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC\u201988). 1\u201310."},{"key":"e_1_3_3_6_2","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Ben-Sasson Eli","year":"2018","unstructured":"Eli Ben-Sasson, Iddo Bentov, Ynon 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\u201918). Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2017\/134"},{"key":"e_1_3_3_7_2","first-page":"46","article-title":"Scalable, transparent, and post-quantum secure computational integrity","volume":"2018","author":"Ben-Sasson Eli","year":"2018","unstructured":"Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive 2018, 46. Retrieved from http:\/\/eprint.iacr.org\/2018\/046","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_23"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36033-7_19"},{"key":"e_1_3_3_10_2","first-page":"828","article-title":"Aurora: Transparent succinct arguments for R1CS","volume":"2018","author":"Ben-Sasson Eli","year":"2018","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. 2018. Aurora: Transparent succinct arguments for R1CS. IACR Cryptology ePrint Archive 2018, 828. Retrieved from https:\/\/eprint.iacr.org\/2018\/828","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.5"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.24"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-004-0135-x"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_7"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_3_3_17_2","first-page":"1","volume-title":"Theory of Cryptography","author":"Chiesa Alessandro","year":"2019","unstructured":"Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. 2019. Succinct arguments in the quantum random oracle model. In Theory of Cryptography, Dennis Hofheinz and Alon Rosen (Eds.). Springer International Publishing, Cham, 1\u201329."},{"key":"e_1_3_3_18_2","first-page":"1076","article-title":"Fractal: Post-quantum and transparent recursive proofs from holography","volume":"2019","author":"Chiesa Alessandro","year":"2019","unstructured":"Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. 2019. Fractal: Post-quantum and transparent recursive proofs from holography. IACR Cryptology ePrint Archive 2019, 1076. Retrieved from https:\/\/eprint.iacr.org\/2019\/1076","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.64"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_30"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129780"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354258"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_6"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/080725398"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_32"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_18"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214035"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1023"},{"key":"e_1_3_3_31_2","volume-title":"Algebra (3rd ed.)","author":"Lang Serge","year":"2002","unstructured":"Serge Lang. 2002. Algebra (3rd ed.). Springer."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73014"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_3_35_2","unstructured":"Ron M. Roth and Gilles Z\u00e9mor. 2018. Personal communication."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488709"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_3_3_38_2","volume-title":"Computationally Efficient Error-correcting Codes and Holographic Proofs","author":"Spielman Daniel A.","year":"1995","unstructured":"Daniel A. Spielman. 1995. Computationally Efficient Error-correcting Codes and Holographic Proofs. Ph.D. Dissertation. MIT."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3614423","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3614423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:30Z","timestamp":1750287030000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3614423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,11]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3614423"],"URL":"https:\/\/doi.org\/10.1145\/3614423","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,11]]},"assertion":[{"value":"2021-07-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}