The Untold Story of $$\mathsf {SBP}$$

DOI10.1007/978-3-030-50026-9_29OpenAlexW3036812112MaRDI QIDQ5042261

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

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• The complexity of estimating min-entropy
• A framework for non-interactive instance-dependent commitment schemes (NIC)
• If NP has polynomial-size circuits, then MA=AM
• Derandomizing Arthur-Merlin games using hitting sets
• Relative complexity of checking and evaluating
• Simulating BPP using a general weak random source
• On relationships between statistical zero-knowledge proofs
• Error-bounded probabilistic computations between MA and AM
• A Sample of Samplers: A Computational Perspective on Sampling
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• A complete problem for statistical zero knowledge
• The Knowledge Complexity of Interactive Proof Systems
• On the Accepting Density Hierarchy in NP
• On the Power of Statistical Zero Knowledge
• Computational Complexity
• Rectangles Are Nonnegative Juntas

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