The landscape of communication complexity classes
From MaRDI portal
Publication:1653337
DOI10.1007/s00037-018-0166-6zbMath1398.68180OpenAlexW2793039178WikidataQ130114313 ScholiaQ130114313MaRDI QIDQ1653337
Publication date: 3 August 2018
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6199/
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (16)
Amplification with one \textsf{NP} oracle query ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Predicate encryption from bilinear maps and one-sided probabilistic rank ⋮ Communication complexity with small advantage ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Equality alone does not simulate randomness ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Unnamed Item ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- On a theorem of Razborov
- Probabilistic communication complexity
- An information statistics approach to data stream and communication complexity
- Boolean function complexity. Advances and frontiers.
- Relations between communication complexity classes
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- Halfspace matrices
- The 1-versus-2 queries problem revisited
- On the complexity of succinct zero-sum games
- The complexity of facets (and some facets of complexity)
- NP is as easy as detecting unique solutions
- Bounded queries to SAT and the Boolean hierarchy
- Private vs. common random bits in communication complexity
- Results on communication complexity classes
- On the distributional complexity of disjointness
- Symmetric alternation captures BPP
- Hardness vs randomness
- Non-deterministic communication complexity with few witnesses
- More on BPP and the polynomial-time hierarchy
- 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
- A linear lower bound on the unbounded error probabilistic communication complexity.
- On relations between counting communication complexity classes
- On unique satisfiability and the threshold behavior of randomized reductions
- A short proof that the extension complexity of the correlation polytope grows exponentially
- Arthur-Merlin streaming complexity
- The unbounded-error communication complexity of symmetric functions
- On zero error algorithms having oracle access to one query
- Error-bounded probabilistic computations between MA and AM
- A strong direct product theorem for disjointness
- Algebrization
- Streaming computations with a loquacious prover
- Non-Interactive Proofs of Proximity
- The Sign-Rank of AC$^0$
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Divergence measures based on the Shannon entropy
- The Pattern Matrix Method
- On the unique satisfiability problem
- PP is as Hard as the Polynomial-Time Hierarchy
- Complexity Lower Bounds using Linear Algebra
- On Graph Complexity
- Relative Discrepancy Does not Separate Information and Communication Complexity
- Learning Complexity vs Communication Complexity
- Two applications of information complexity
- Annotations in Data Streams
- Threshold Computation and Cryptographic Security
- Communication Complexity
- En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
- An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
- Quantum computing, postselection, and probabilistic polynomial-time
- Lower Bounds for Quantum Communication Complexity
- Rectangles Are Nonnegative Juntas
- Exponential Separation of Information and Communication for Boolean Functions
This page was built for publication: The landscape of communication complexity classes
