Lower bounds in communication complexity
From MaRDI portal
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Information theory (general) (94A15)
Recommendations
Cited in
(47)- Lower bounds on the multiparty communication complexity
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Information complexity and applications.
- Counting the number of perfect matchings, and generalized decision trees
- Upper bounds on communication in terms of approximate rank
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Bounds on the number of 2-level polytopes, cones, and configurations
- Dimension-free bounds and structural results in communication complexity
- Communication complexity and orthogonal polynomials
- Fooling pairs in randomized communication complexity
- Heuristics for exact nonnegative matrix factorization
- Grothendieck-type inequalities in combinatorial optimization
- scientific article; zbMATH DE number 6691438 (Why is no real title available?)
- Space-bounded communication complexity
- Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Communication complexity (for algorithm designers)
- The pattern matrix method
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- Lower bounds on information complexity via zero-communication protocols and applications
- Fractional Covers and Communication Complexity
- Multiparty communication complexity of vector-valued and sum-type functions
- scientific article; zbMATH DE number 1421021 (Why is no real title available?)
- A candidate for a strong separation of information and communication
- Exponential separation of communication and external information
- Communication complexity of correlated equilibrium with small support
- Approximate Degree in Classical and Quantum Computing
- Classical algorithms from quantum and Arthur-Merlin communication protocols
- scientific article; zbMATH DE number 7561760 (Why is no real title available?)
- A comparison of two lower bound methods for communication complexity (extended abstract)
- A lifting theorem with applications to symmetric functions
- Communication Lower Bounds Via the Chromatic Number
- Communication lower bounds using directional derivatives
- Quantum state complexity of formal languages
- String Matching: Communication, Circuits, and Learning.
- Around the log-rank conjecture
- Depth-3 circuits for inner product
- Upper bounds on communication in terms of approximate rank
- On parity decision trees for Fourier-sparse Boolean functions
- A hierarchy of constant communication complexity
- A direct product theorem for quantum communication complexity with applications to device-independent cryptography
- On parity decision trees for Fourier-sparse Boolean functions
- Communication memento: memoryless communication complexity
- Consumable data via quantum communication
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- New bounds on the half-duplex communication complexity
- Some order dimension bounds for communication complexity problems
This page was built for publication: Lower bounds in communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3404184)
