loading...
Randomised Individual Communication Complexity
June 22-June 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2008.332008 IEEE 23rd Annual Conference on C ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
In this paper we study the individual communication complexity of the following problem. Alice receives an input string x and Bob an input string y, and Alice has to output y. For deterministic protocols it has been shown in Buhrman et al. (2004), that C(y) many bits need to be exchanged even if the actual amount of information C(y|x) is much smaller than C(y). It turns out that for randomised protocols the situation is very different. We establish randomised protocols whose communication complexity is close to the information theoretical lower bound. We furthermore initiate and obtain results about the randomised round complexity of this problem and show trade-offs between the amount of communication and the number of rounds. In order to do this we establish a general framework for studying these types of questions.
Index Terms:
individual communication complexity, randomized protocols, rounds, Kolmogorov complexity
Citation:
Harry Buhrman, Michal Kouck?, Nikolai Vereshchagin, "Randomised Individual Communication Complexity," ccc, pp.321-331, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008
Usage of this product signifies your acceptance of the Terms of Use.