The Untold Story of \mathsf {SBP}

DOI10.1007/978-3-030-50026-9_29MaRDI QIDQ5042261zbMATH OpenOpenAlexFDO

Authors Ilya Volkovich

Publication date 19 October 2022

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-50026-9_29

zbMATH Keywords

\( \mathsf{NP}\) problems with bounded number of solutions\( \mathsf{SZK} \)Arthur-Merlin protocolsrandomized complexity theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A complete problem for statistical zero knowledge
• A framework for non-interactive instance-dependent commitment schemes (NIC)
• A sample of samplers: a computational perspective on sampling
• Computational Complexity
• Derandomizing Arthur-Merlin games using hitting sets
• Error-bounded probabilistic computations between MA and AM
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• If NP has polynomial-size circuits, then MA=AM
• On relationships between statistical zero-knowledge proofs
• On the Accepting Density Hierarchy in NP
• On the power of statistical zero knowledge
• Rectangles are nonnegative juntas
• Relative complexity of checking and evaluating
• Simulating BPP using a general weak random source
• The complexity of estimating min-entropy
• The Knowledge Complexity of Interactive Proof Systems

This page was built for publication: The Untold Story of $$\mathsf {SBP}$$

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