Abstract | ||
---|---|---|
We develop a new local characterization of the zero-error information complexity function for two-party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: IC(AND,0) = C∧≅ 1.4923 bits, and ICext(AND,0) = log2 3 ≅ 1.5839 bits. This leads to a tight (upper and lower bound) characterization of the communication complexity of the set intersection problem on subsets of {1,...,n} (the player are required to compute the intersection of their sets), whose randomized communication complexity tends to C∧⋅ n pm o(n) as the error tends to zero. The information-optimal protocol we present has an infinite number of rounds. We show this is necessary by proving that the rate of convergence of the r-round information cost of AND to IC(AND,0)=C∧ behaves like Θ(1/r2), i.e. that the r-round information complexity of AND is C∧+Θ(1/r2). We leverage the tight analysis obtained for the information complexity of AND to calculate and prove the exact communication complexity of the set disjointness function Disjn(X,Y) = - vi=1n AND(xi,yi) with error tending to 0, which turns out to be = CDISJ⋅ n pm o(n), where CDISJ≅ 0.4827. Our rate of convergence results imply that an asymptotically optimal protocol for set disjointness will have to use ω(1) rounds of communication, since every r-round protocol will be sub-optimal by at least Ω(n/r2) bits of communication. We also obtain the tight bound of 2/ln2 k pm o(k) on the communication complexity of disjointness of sets of size ≤ k. An asymptotic bound of Θ(k) was previously shown by Hastad and Wigderson. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2488608.2488628 | Proceedings of the forty-fifth annual ACM symposium on Theory of computing |
Keywords | DocType | Citations |
set disjointness,external information complexity,information complexity,r-round information complexity,exact communication complexity,communication complexity,zero-error information complexity function,n pm o,two-party communication problem,randomized communication complexity | Journal | 20 |
PageRank | References | Authors |
1.11 | 19 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mark Braverman | 1 | 810 | 61.60 |
Ankit Garg | 2 | 125 | 16.19 |
Denis Pankratov | 3 | 71 | 7.81 |
Omri Weinstein | 4 | 55 | 5.17 |