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(AND0)=C14923 bits, and ICext(AND0)=log2315839 bits. This leads to a tight (upper and lower bound) characterization of the communication complexity of the set intersection problem on subsets of 1n , whose randomized communication complexity tends to Cno(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(AND0)=C behaves like (1r2) , i.e. that the r-round information complexity of AND is C+(1r2) .

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(XY)=ni=1AND(xiyi) with error tending to 0, which turns out to be =CDISJno(n), where CDISJ04827. Our rate of convergence results imply that an 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 (nr2) bits of communication.

We also obtain the tight bound of 2ln2ko(k) on the communication complexity of disjointness of sets of size k. An asymptotic bound of (k) was previously shown by Hastad and Wigderson.