{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T14:08:01Z","timestamp":1770818881101,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T00:00:00Z","timestamp":1739491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-1909216 and CCF-1909683"],"award-info":[{"award-number":["CCF-1909216 and CCF-1909683"]}]},{"name":"National Science Foundation","award":["CNS-2150186 and CCF-1852215"],"award-info":[{"award-number":["CNS-2150186 and CCF-1852215"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>\n            We show that the space-bounded statistical zero knowledge classes\n            <jats:sans-serif>\n              SZK\n              <jats:sub>L<\/jats:sub>\n            <\/jats:sans-serif>\n            and\n            <jats:sans-serif>\n              NISZK\n              <jats:sub>L<\/jats:sub>\n            <\/jats:sans-serif>\n            are surprisingly robust, in that the power of the verifier and simulator can be strengthened or weakened without affecting the resulting class.Coupled with other recent characterizations of these classes [\n            <jats:xref ref-type=\"bibr\">5<\/jats:xref>\n            ], this can be viewed as lending support to the conjecture that these classes may coincide with the non-space-bounded classes\n            <jats:sans-serif>SZK<\/jats:sans-serif>\n            and\n            <jats:sans-serif>NISZK<\/jats:sans-serif>\n            , respectively.\n          <\/jats:p>","DOI":"10.1145\/3708508","type":"journal-article","created":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T11:23:54Z","timestamp":1734434634000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Robustness for Space-Bounded Statistical Zero Knowledge"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0650-028X","authenticated-orcid":false,"given":"Eric","family":"Allender","sequence":"first","affiliation":[{"name":"Dept. of Computer Science, Rutgers The State University of New Jersey, New Brunswick, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1894-5315","authenticated-orcid":false,"given":"Jacob","family":"Gray","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, University of Toronto, Toronto, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6825-7112","authenticated-orcid":false,"given":"Saachi","family":"Mutreja","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, Columbia University, New York, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4600-3675","authenticated-orcid":false,"given":"Harsha","family":"Tirumala","sequence":"additional","affiliation":[{"name":"Dept. of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, United States"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-2700-8363","authenticated-orcid":false,"given":"Pengxiang","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Sciences, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2025,2,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3586165.3586175"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.10.040"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","unstructured":"Eric Allender Jacob Gray Saachi Mutreja Harsha Tirumala and Pengxiang Wang. 2023. Robustness for space-bounded statistical zero knowledge. In Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM 2023) Nicole Megow and Adam Smith (Eds.). Leibniz International Proceedings in Informatics Vol. 275. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik Dagstuhl Germany Article 56 21 pages. DOI:10.4230\/LIPIcs.APPROX\/RANDOM.2023.56","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2023.56"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3349616"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","unstructured":"Eric Allender Shuichi Hirahara and Harsha Tirumala. 2023. Kolmogorov complexity characterizes statistical zero knowledge. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) Yael Tauman Kalai (Ed.). Leibniz International Proceedings in Informatics (LIPIcs) Vol. 251. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik Dagstuhl Germany Article 3 19 pages. DOI:10.4230\/LIPIcs.ITCS.2023.3","DOI":"10.4230\/LIPIcs.ITCS.2023.3"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.10.005"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1996300100011"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1646"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0280-6"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28409"},{"key":"e_1_3_3_13_2","article-title":"Algorithms for Boolean formula evaluation and for tree contraction","author":"Buss Samuel R.","year":"1993","unstructured":"Samuel R. Buss. 1993. Algorithms for Boolean formula evaluation and for tree contraction. In Arithmetic, Proof Theory, and Computational Complexity, Peter Clote and Jan Krajicek (Eds.). Oxford Science Publications, 96\u2013115.","journal-title":"Arithmetic, Proof Theory, and Computational Complexity, Peter Clote and Jan Krajicek (Eds.). Oxford Science Publications, 96\u2013115."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","unstructured":"Ronald Cramer Serge Fehr Yuval Ishai and Eyal Kushilevitz. 2003. Efficient multi-party computation over rings. In Advances in Cryptology\u2014EUROCRYPT 2003. Lecture Notes in Computer Science Vol. 2656. Springer 596\u2013613. DOI:10.1007\/3-540-39200-9_37","DOI":"10.1007\/3-540-39200-9_37"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","unstructured":"Alfredo De Santis Giovanni Di Crescenzo Giuseppe Persiano and Moti Yung. 1998. Image density is complete for non-interactive-SZK (extended abstract). In Automata Languages and Programming (ICALP 1998). Lecture Notes in Computer Science Vol. 1443. Springer 784\u2013795. DOI:10.1007\/BFb0055102","DOI":"10.1007\/BFb0055102"},{"key":"e_1_3_3_16_2","first-page":"460","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science","author":"Dvir Zeev","year":"2011","unstructured":"Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, and Salil P. Vadhan. 2011. On approximating the entropy of polynomial mappings. In Proceedings of the 2nd Symposium on Innovations in Computer Science. 460\u2013475."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3278158"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48405-1_30"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276852"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00091-0"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","unstructured":"Yuval Ishai and Eyal Kushilevitz. 2002. Perfect constant-round secure computation via perfect randomizing polynomials. In Automata Languages and Programming (ICALP 2002). Lecture Notes in Computer Science Vol. 2380. Springer 244\u2013256. DOI:10.1007\/3-540-45465-9_22","DOI":"10.1007\/3-540-45465-9_22"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216058"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1664"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","unstructured":"Chris Peikert and Vinod Vaikuntanathan. 2008. Noninteractive statistical zero-knowledge proofs for lattice problems. In Advances in Cryptology (CRYPTO 2008). Lecture Notes in Computer Science Vol. 5157. Springer 536\u2013553. DOI:10.1007\/978-3-540-85174-5_30","DOI":"10.1007\/978-3-540-85174-5_30"},{"key":"e_1_3_3_28_2","volume-title":"Simple Reductions to Circuit Minimization: DIMACS REU Report","author":"Ramesh Vishal","year":"2021","unstructured":"Vishal Ramesh, Sasha Sami, and Noah Singer. 2021. Simple Reductions to Circuit Minimization: DIMACS REU Report. Technical Report. DIMACS, Rutgers University."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636868"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970241096X"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:55Z","timestamp":1750295395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,14]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3708508"],"URL":"https:\/\/doi.org\/10.1145\/3708508","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,14]]},"assertion":[{"value":"2023-10-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}