Kolmogorov complexity and combinatorial methods in communication complexity
DOI10.1016/J.TCS.2010.10.044zbMATH Open1216.68134OpenAlexW2174675778MaRDI QIDQ534568FDOQ534568
Authors: Sophie Laplante, Marc Kaplan 
Publication date: 18 May 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.044
Recommendations
- Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
- Logical Approaches to Computational Barriers
- Individual communication complexity
- New bounds on classical and quantum one-way communication complexity
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)
Cites Work
- A Mathematical Theory of Communication
- Title not available (Why is that?)
- Exponential Separation of Quantum and Classical One-Way Communication Complexity
- Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
- Communication Complexity
- An introduction to Kolmogorov complexity and its applications
- Two applications of information complexity
- Quantum communication complexity of symmetric predicates
- An information statistics approach to data stream and communication complexity
- Disjointness is hard in the multiparty number-on-the-forehead model
- On randomized one-round communication complexity
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- Title not available (Why is that?)
- Lower bounds in communication complexity based on factorization norms
- Title not available (Why is that?)
- Title not available (Why is that?)
- New applications of the incompressibility method. II
- Fourier analysis for probabilistic communication complexity
- Individual communication complexity
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Title not available (Why is that?)
Cited In (6)
- Title not available (Why is that?)
- Communication complexity and combinatorial lattice theory
- Logical Approaches to Computational Barriers
- Title not available (Why is that?)
- Randomized communication complexity of approximating Kolmogorov complexity
- Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
This page was built for publication: Kolmogorov complexity and combinatorial methods in communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534568)
