Robustness for space-bounded statistical zero knowledge

DOI10.1145/3708508MaRDI QIDQ6994670zbMATH OpenFDO

Authors Eric Allender, Jacob Gray, Saachi Mutreja, Pengxiang Wang

Publication date 23 April 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3708508

zbMATH Keywords

interactive proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites work

• A complete problem for statistical zero knowledge
• A note on closure properties of logspace MOD classes
• A universal tree balancing theorem
• Classifying problems on linear congruences and Abelian permutation groups using logspace counting classes
• Complexity of regular functions
• Constant depth circuits, Fourier transform, and learnability
• Constructing a perfect matching is in random NC
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Cryptography in NC^0
• scientific article; zbMATH DE number 440476 (Why is no real title available?)
• scientific article; zbMATH DE number 2009982 (Why is no real title available?)
• scientific article; zbMATH DE number 1775425 (Why is no real title available?)
• scientific article; zbMATH DE number 2086626 (Why is no real title available?)
• scientific article; zbMATH DE number 1418312 (Why is no real title available?)
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Kolmogorov complexity characterizes statistical zero knowledge
• New insights on the (non-)hardness of circuit minimization and related problems
• Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems
• On relationships between statistical zero-knowledge proofs
• On the Hardness of Graph Isomorphism
• Relationships among $PL$, $\#L$, and the determinant
• Robustness for space-bounded statistical zero knowledge
• The Parallel Complexity of Abelian Permutation Group Problems

Cited in

(1)

• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: Robustness for space-bounded statistical zero knowledge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6994670)