Zero-information protocols and unambiguity in Arthur-Merlin communication
From MaRDI portal
Publication:343848
DOI10.1007/s00453-015-0104-9zbMath1352.94004OpenAlexW2281178725MaRDI QIDQ343848
Publication date: 29 November 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0104-9
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12) Communication theory (94A05)
Related Items (12)
Upslices, downslices, and secret-sharing with complexity of \(1.5^n\) ⋮ The landscape of communication complexity classes ⋮ Predicate encryption from bilinear maps and one-sided probabilistic rank ⋮ Unnamed Item ⋮ Communication and information complexity ⋮ Zero-Knowledge Proofs of Proximity ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ The complexity of quantum disjointness ⋮ Unnamed Item ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On a theorem of Razborov
- An information statistics approach to data stream and communication complexity
- Boolean function complexity. Advances and frontiers.
- Problems complete for \(\oplus L\)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Relativized Arthur-Merlin versus Merlin-Arthur games
- On the distributional complexity of disjointness
- Probabilistic complexity classes and lowness
- Non-deterministic communication complexity with few witnesses
- A note on non-deterministic communication complexity with few witnesses
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Graph complexity
- PP is closed under intersection
- Arthur-Merlin streaming complexity
- Error-bounded probabilistic computations between MA and AM
- A minimal model for secure computation (extended abstract)
- A strong direct product theorem for disjointness
- Two Results about Quantum Messages
- The Hardness of Being Private
- Algebrization
- Streaming computations with a loquacious prover
- Non-Interactive Proofs of Proximity
- Sparse and Lopsided Set Disjointness via Information Theory
- Divergence measures based on the Shannon entropy
- Complexity Lower Bounds using Linear Algebra
- On Graph Complexity
- Learning Complexity vs Communication Complexity
- Two applications of information complexity
- Annotations in Data Streams
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- Privacy and Communication Complexity
- Communication Complexity
- Boolean complexity classes vs. their arithmetic analogs
- Making Nondeterminism Unambiguous
- Annotations in Data Streams
- An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
- An axiomatic approach to algebrization
- Annotations for Sparse Data Streams
- Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
- Lower Bounds for Quantum Communication Complexity
- From information to exact communication
- An information complexity approach to extended formulations
- Univariate Discrete Distributions
- Cryptography in $NC^0$
- Rectangles Are Nonnegative Juntas
This page was built for publication: Zero-information protocols and unambiguity in Arthur-Merlin communication
