Logo image
Back
Robustness for space-bounded statistical zero knowledge
Conference proceeding   Open access   Peer reviewed

Robustness for space-bounded statistical zero knowledge

Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala and Pengxiang Wang
LIPIcs : Leibniz international proceedings in informatics, Vol.275, pp.56:1-56:21
International Workshop on Randomization and Computation (RANDOM 2023) (Atlanta, GA, 09/11/2023–09/13/2023)
09/04/2023
DOI: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.56

Abstract

2012 ACM Subject Classification Theory of computation → Complexity classes; Theory of compu-
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, 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.
pdf
agmtw746.41 kBDownloadView
Version of Record (VoR) Open Access
url
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.56View
Version of Record (VoR)
url
Report an accessibility issueView
Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

88 File downloads
48 Record Views

Details

Logo image