A hierarchy of constant communication complexity
From MaRDI portal
Cites work
- A direct product theorem for quantum communication complexity with applications to device-independent QKD
- A discrepancy lower bound for information complexity
- A linear lower bound on the unbounded error probabilistic communication complexity.
- An information statistics approach to data stream and communication complexity
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Classical and quantum partition bound and detector inefficiency
- Communication complexity of set-disjointness for all probabilities
- Communication complexity under product and nonproduct distributions
- Communication is bounded by root of rank
- Complexity measures of sign matrices
- Dimension-free bounds and structural results in communication complexity
- Exponential separation of information and communication for Boolean functions
- Exponential separation of quantum communication and classical information
- Factorization norms and hereditary discrepancy
- From information to exact communication
- Geometric arguments yield better bounds for threshold circuits and distributed computing
- Halfspace matrices
- How to compress interactive communication
- scientific article; zbMATH DE number 176776 (Why is no real title available?)
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- scientific article; zbMATH DE number 1142305 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 6829278 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- scientific article; zbMATH DE number 761425 (Why is no real title available?)
- scientific article; zbMATH DE number 773999 (Why is no real title available?)
- scientific article; zbMATH DE number 7204275 (Why is no real title available?)
- scientific article; zbMATH DE number 4197419 (Why is no real title available?)
- scientific article; zbMATH DE number 5485573 (Why is no real title available?)
- scientific article; zbMATH DE number 7650381 (Why is no real title available?)
- Information Equals Amortized Communication
- Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
- Interactive information complexity
- Learning complexity vs communication complexity
- Linear algebraic methods in communication complexity
- Lower bound methods for sign-rank and their limitations
- Lower bounds for elimination via weak regularity
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Lower Bounds for Quantum Communication Complexity
- Lower bounds for union-split-find related problems on random access machines
- Lower bounds in communication complexity
- Lower bounds in communication complexity based on factorization norms
- Lower bounds on information complexity via zero-communication protocols and applications
- Lower bounds on threshold and related circuits via communication complexity
- Lower bounds to the complexity of symmetric Boolean functions
- Meanders and their applications in lower bounds arguments
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Near-optimal bounds on bounded-round quantum communication complexity of disjointness
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- New bounds on classical and quantum one-way communication complexity
- On public-coin zero-error randomized communication complexity
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- On randomized one-round communication complexity
- On the density of families of sets
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- One-way communication complexity and non-adaptive decision trees
- One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size
- Optimal private halfspace counting via discrepancy
- Optimal Quantum Source Coding With Quantum Side Information at the Encoder and Decoder
- Property testing bounds for linear and quadratic functions via parity decision trees
- Quantum information complexity
- Randomized communication and implicit graph representations
- Randomized communication and implicit representations for matrices and graphs of small sign-rank
- Real rank versus nonnegative rank
- Relative discrepancy does not separate information and communication complexity
- Rényi information complexity and an information theoretic characterization of the partition bound
- Separation of the factorization norm and randomized communication complexity
- Sign rank vs discrepancy
- Sketching distances in monotone graph classes
- Some Results on Distributed Source Coding for Interactive Function Computation
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Streaming and communication complexity of clique approximation
- Superpolynomial lower bounds for monotone span programs
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
- The landscape of communication complexity classes
- The power of factorization mechanisms in local and central differential privacy
- The Quantum Communication Complexity of Sampling
- The unbounded-error communication complexity of symmetric functions
- Three models for the description of language
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Upper bounds on communication in terms of approximate rank
- Worst-case interactive communication. II. Two messages are not optimal
- Zero-information protocols and unambiguity in Arthur-Merlin communication (extended abtract)
This page was built for publication: A hierarchy of constant communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6841903)
