We develop a new characterization of the zero-error information complexity for two-party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function. Respectively, it is 1.4923... and 1.5839... bits. This leads to a tight characterization (up to sub linear terms) of the communication complexity of the set intersection problem, whose randomized communication complexity tends to 1.4923... n+o(n) as the error tends to zero.

The information-optimal protocol for AND we present has an infinite number of rounds. We show that this is necessary by proving that the rate of convergence of the r-round information cost of AND to 1.4923... behaves like 1/r^2.

We further obtain exact communication complexity (up to sub linear terms) of the set disjointness with error tending to 0. Our rate of convergence results imply that an optimal protocol for the set disjointness will have to use super-constant number of rounds of communication.

Joint work with Mark Braverman, Ankit Garg, and Omri Weinstein.