Kolmogorov complexity and combinatorial methods in communication complexity

DOI10.1016/J.TCS.2010.10.044zbMath1216.68134OpenAlexW2174675778MaRDI QIDQ534568

Sophie Laplante, M. A. 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

zbMATH Keywords

Kolmogorov complexityinformation theorycommunication complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• 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
• Fourier analysis for probabilistic communication complexity
• New applications of the incompressibility method. II
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• Individual communication complexity
• Two applications of information complexity
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• Quantum communication complexity of symmetric predicates
• Communication Complexity
• An introduction to Kolmogorov complexity and its applications
• Lower bounds in communication complexity based on factorization norms

This page was built for publication: Kolmogorov complexity and combinatorial methods in communication complexity