Paper Info
Title
Individual communication complexity
Abstract
We initiate the theory of communication complexity of individual inputs held by the agents. This contrasts with the usual communication complexity model, where one counts the amount of communication for the worst-case or the average-case inputs. The individual communication complexity gives more information (the worst-case and the average-case can be derived from it but not vice versa) and may in some cases be of more interest. It is given in terms of the Kolmogorov complexities of the individual inputs. There are different measures of communication complexity depending on whether the protocol is guaranteed to be correct for all inputs or not, and whether there's one-way or two-way communication. Bounds are provided for the communication of specific functions and connections between the different communication measures are shown. Some counter-intuitive results: for deterministic protocols that need to communicate Bob's input to Alice they need to communicate all of Bob's input (rather than the information difference with Alice's input), and there are so-called ''non-communicable'' inputs.
Year
DOI
Venue
2007
10.1016/j.jcss.2007.03.015
J. Comput. Syst. Sci.
Keywords
Field
DocType
information difference,different measure,communication complexity,different communication measure,two-way communication,usual communication complexity model,kolmogorov complexity,individual input,individual complexity,individual communication complexity,average-case input,communication theory
Discrete mathematics,Computer science,Communication theory,Algorithm,Theoretical computer science,Communication complexity
Journal
Volume
Issue
ISSN
73
6
Journal of Computer and System Sciences
Citations 
PageRank 
References 
3
0.40
8
Authors
4
Name
Order
Citations
PageRank
Harry Buhrman11607117.99
Hartmut Klauck248430.85
Nikolai K. Vereshchagin314215.89
Paul Vitányi42130287.76