Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1109/CCC.2002.1004344 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
communication complexity,information theory,maximum likelihood estimation,VC-dimension,arbitrary groups,communication complexity,generalized addressing function problem,inequality,information theory,lower bounds,maximum likelihood estimate principle,multi-party communication model,multi-party set disjointness problem,one-way communication model,product distributions,shatter coefficients,simultaneous communication model | Information theory,Discrete mathematics,VC dimension,Fano's inequality,Computer science,Upper and lower bounds,Models of communication,Communication complexity,Equivalence (measure theory),Function problem | Conference |
ISSN | Citations | PageRank |
1093-0159 | 44 | 3.30 |
References | Authors | |
20 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ziv Bar-Yossef | 1 | 1776 | 118.00 |
T. S. Jayram | 2 | 1373 | 75.87 |
Ravi Kumar | 3 | 13932 | 1642.48 |
D. Sivakumar | 4 | 3515 | 389.02 |