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