### 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 IC^{ext}(AND, 0) = log_{2} 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/r^{2}). 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 Disj_{n}(X, Y) = ¬ ∨^{n}_{i =1} AND(x_{i}, y_{i}) with error tending to 0, which turns out to be = CDISJ · n ± o(n), where C_{DISJ} ≈ 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/r^{2}) 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.

Original language | English (US) |
---|---|

Title of host publication | STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing |

Pages | 151-160 |

Number of pages | 10 |

DOIs | |

State | Published - Jul 11 2013 |

Event | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | Palo Alto, CA |

Period | 6/1/13 → 6/4/13 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Communication complexity
- Disjointness
- Information complexity

## Fingerprint Dive into the research topics of 'From information to exact communication'. Together they form a unique fingerprint.

## Cite this

*STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing*(pp. 151-160). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488628