TY - GEN

T1 - From information to exact communication

AU - Braverman, Mark

AU - Garg, Ankit

AU - Pankratov, Denis

AU - Weinstein, Omri

PY - 2013

Y1 - 2013

N2 - 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 ± 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/r 2), 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) = ¬ ∨ni =1 AND(xi, yi) with error tending to 0, which turns out to be = CDISJ · n ± 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 rround protocol will be sub-optimal by at least Ω(n/r2) bits of communication. We also obtain the tight bound of 2/ ln 2k ± o(k) on the communication complexity of disjointness of sets of size ≤ k. An asymptotic bound of Θ(k) was previously shown by Håstad and Wigderson.

AB - 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 ± 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/r 2), 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) = ¬ ∨ni =1 AND(xi, yi) with error tending to 0, which turns out to be = CDISJ · n ± 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 rround protocol will be sub-optimal by at least Ω(n/r2) bits of communication. We also obtain the tight bound of 2/ ln 2k ± o(k) on the communication complexity of disjointness of sets of size ≤ k. An asymptotic bound of Θ(k) was previously shown by Håstad and Wigderson.

KW - Communication complexity

KW - Disjointness

KW - Information complexity

UR - http://www.scopus.com/inward/record.url?scp=84879812422&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879812422&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488628

DO - 10.1145/2488608.2488628

M3 - Conference contribution

AN - SCOPUS:84879812422

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 151

EP - 160

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -