Kolmogorov complexity and combinatorial methods in communication complexity

DOI10.1016/J.TCS.2010.10.044MaRDI QIDQ534568zbMATHOpenAlexFDO

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

zbMATH Keywords

information theorycommunication complexityKolmogorov complexity

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 5899240 (Why is no real title available?)
• scientific article; zbMATH DE number 3967876 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2086398 (Why is no real title available?)
• scientific article; zbMATH DE number 5485573 (Why is no real title available?)
• A Mathematical Theory of Communication
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• An information statistics approach to data stream and communication complexity
• An introduction to Kolmogorov complexity and its applications
• Communication Complexity
• Disjointness is hard in the multiparty number-on-the-forehead model
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Fourier analysis for probabilistic communication complexity
• Individual communication complexity
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Lower bounds in communication complexity based on factorization norms
• New applications of the incompressibility method. II
• On randomized one-round communication complexity
• Quantum communication complexity of symmetric predicates
• Two applications of information complexity

Cited in

(6)

• scientific article; zbMATH DE number 2038719 (Why is no real title available?)
• Communication complexity and combinatorial lattice theory
• scientific article; zbMATH DE number 66621 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
• Randomized communication complexity of approximating Kolmogorov 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)