Kolmogorov complexity characterizes statistical zero knowledge

DOI10.4230/LIPICS.ITCS.2023.3MaRDI QIDQ6610263zbMATH OpenFDO

Authors Eric Allender, Shuichi Hirahara

Publication date 25 September 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2023.3

zbMATH Keywords

interactive proofsKolmogorov complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A complete problem for statistical zero knowledge
• scientific article; zbMATH DE number 1418312
• On relationships between statistical zero-knowledge proofs
• scientific article; zbMATH DE number 1256785
• scientific article; zbMATH DE number 1405650

Cited in

(4)

• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• Lower bounds for Levin-Kolmogorov complexity
• Robustness for space-bounded statistical zero knowledge
• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: Kolmogorov complexity characterizes statistical zero knowledge

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