loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
17th Annual IEEE Conference on Computational Complexity (CCC'02)
Information Theory Methods in Communication Complexity
Montreal, Canada
May 21-May 24
ISBN: 0-7695-1468-5
Ziv Bar-Yossef, University of California at Berkeley
T. S. Jayram, IBM Almaden Research Center
Ravi Kumar, IBM Almaden Research Center
D. Sivakumar, IBM Almaden Research Center
We use tools and techniques from information theory to study communication complexity problems in the one-way and simultaneous communication models. Our results include: (1) A tight characterization of multi-party one-way communication complexity for product distributions in terms of VC-dimension and shatter coefficients; (2) An equivalence of multi-party one-way and simultaneous communication models for product distributions; (3) A suite of lower bounds for specific functions in the simultaneous communication model, most notably an optimal lower bound for the multi-party set disjointness problem of Alon et al. (1999) and for the generalized addressing function problem of Babai et al. (1996) for arbitrary groups. Methodologically, our main contribution is rendering communication complexity problems in the framework of information theory. This allows us access to the powerful calculus of information theory and the use of fundamental principles such as Fano's inequality and the Maximum Likelihood Estimate Principle.
Index Terms:
Communication complexity, Fano's inequality, Maximum Likelihood Estimate Principle, Information Theory
Citation:
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, "Information Theory Methods in Communication Complexity," ccc, pp.0093, 17th Annual IEEE Conference on Computational Complexity (CCC'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.