The landscape of communication complexity classes
type: Item
instance of: scholarly article
title: The landscape of communication complexity classes
zbMATH Open document ID: 1398.68180
author: Y. Aharonov
published in: Computational Complexity
publication date: 2018-08-03T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6199/
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6913671
zbMATH Keywords: communication complexity
zbMATH Keywords: complexity classes
MaRDI profile type: Publication
OpenAlex ID: W2793039178
cites work: Quantum computing, postselection, and probabilistic polynomial-time
cites work: Algebrization
cites work: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
cites work: An information statistics approach to data stream and communication complexity
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: On the unique satisfiability problem
cites work: Error-bounded probabilistic computations between MA and AM
cites work: The Pattern Matrix Method
cites work: \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
cites work: On zero error algorithms having oracle access to one query
cites work: More on BPP and the polynomial-time hierarchy
cites work: On the distributional complexity of disjointness
cites work: Annotations in Data Streams
cites work: Q4601830
cites work: On unique satisfiability and the threshold behavior of randomized reductions
cites work: The complexity of facets (and some facets of complexity)
cites work: Hardness vs randomness
cites work: On relations between counting communication complexity classes
cites work: Relative Discrepancy Does not Separate Information and Communication Complexity
cites work: A linear lower bound on the unbounded error probabilistic communication complexity.
cites work: On the complexity of succinct zero-sum games
cites work: Exponential Separation of Information and Communication for Boolean Functions
cites work: En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
cites work: Q3002823
cites work: Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
cites work: The unbounded-error communication complexity of symmetric functions
cites work: Learning Complexity vs Communication Complexity
cites work: Rectangles are nonnegative juntas
cites work: Zero-information protocols and unambiguity in Arthur-Merlin communication
cites work: Communication complexity of set-disjointness for all probabilities
cites work: A note on non-deterministic communication complexity with few witnesses
cites work: Arthur-Merlin streaming complexity
cites work: Non-Interactive Proofs of Proximity
cites work: Relations between communication complexity classes
cites work: Threshold Computation and Cryptographic Security
cites work: A short proof that the extension complexity of the correlation polytope grows exponentially
cites work: Two applications of information complexity
cites work: On Graph Complexity
cites work: Boolean function complexity. Advances and frontiers.
cites work: Non-deterministic communication complexity with few witnesses
cites work: Lower Bounds for Quantum Communication Complexity
cites work: A strong direct product theorem for disjointness
cites work: Streaming computations with a loquacious prover
cites work: An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
cites work: Communication Complexity
cites work: Results on communication complexity classes
cites work: Divergence measures based on the Shannon entropy
cites work: Complexity Lower Bounds using Linear Algebra
cites work: Private vs. common random bits in communication complexity
cites work: Probabilistic communication complexity
cites work: Graph complexity
cites work: The Sign-Rank of AC$^0$
cites work: Symmetric alternation captures BPP
cites work: Halfspace matrices
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: The 1-versus-2 queries problem revisited
cites work: Q4164821
cites work: NP is as easy as detecting unique solutions
cites work: Q4263492
cites work: On a theorem of Razborov
Wikidata QID: Q130114313
DOI: 10.1007/S00037-018-0166-6
description: scientific article; zbMATH DE number 6913671