2026-08-09T04:28:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18881 2024-03-06T11:02:49Z ddc:004 open_access

Robustness for Space-Bounded Statistical Zero Knowledge Allender, Eric Gray, Jacob Mutreja, Saachi Tirumala, Harsha Wang, Pengxiang Interactive Proofs We show that the space-bounded Statistical Zero Knowledge classes SZK_L and NISZK_L 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 [Eric Allender et al., 2023], this can be viewed as lending support to the conjecture that these classes may coincide with the non-space-bounded classes SZK and NISZK, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Allender and Jacob Gray and Saachi Mutreja and Harsha Tirumala and Pengxiang Wang 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.56 urn:nbn:de:0030-drops-188815 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.56 eng https://creativecommons.org/licenses/by/4.0/legalcode