Kolmogorov complexity and combinatorial methods in communication complexity
type: Item
instance of: scholarly article
title: Kolmogorov complexity and combinatorial methods in communication complexity
zbMATH Open document ID: 1216.68134
author: Sophie Laplante
author: Marc Kaplan
published in: Theoretical Computer Science
publication date: 2011-05-18T00:00:00Z
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 81P45
zbMATH DE Number: 5895908
zbMATH Keywords: communication complexity
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: information theory
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.10.044
OpenAlex ID: W2174675778
cites work: Exponential Separation of Quantum and Classical One-Way Communication Complexity
cites work: An information statistics approach to data stream and communication complexity
cites work: A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
cites work: New applications of the incompressibility method. II
cites work: Individual communication complexity
cites work: Q4736853
cites work: Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
cites work: Q5302084
cites work: Q4519896
cites work: Two applications of information complexity
cites work: On randomized one-round communication complexity
cites work: Communication Complexity
cites work: Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
cites work: Disjointness is hard in the multiparty number-on-the-forehead model
cites work: An introduction to Kolmogorov complexity and its applications
cites work: Lower bounds in communication complexity based on factorization norms
cites work: Fourier analysis for probabilistic communication complexity
cites work: Quantum communication complexity of symmetric predicates
cites work: A Mathematical Theory of Communication
cites work: Q3002763
cites work: Q3735043
DOI: 10.1016/J.TCS.2010.10.044
description: scientific article; zbMATH DE number 5895908