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_{\wedge}\approx 1.4923 bits, and IC^{ext}(AND,0) = \log_2 3 \approx 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,\ldots,n\}, whose randomized communication complexity tends to C_{\wedge}\cdot 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_\wedge behaves like \Theta(1/r^2), i.e. that the r-round information complexity of AND is C_\wedge+\Theta(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) = \neg \vee_{i=1}^{n} AND(x_i,y_i) with error tending to 0, which turns out to be = C_{DISJ}\cdot n \pm o(n), where C_{DISJ}\approx 0.4827. Our rate of convergence results imply that an optimal protocol for set disjointness will have to use \omega(1) rounds of communication, since every r-round protocol will be sub-optimal by at least \Omega(n/r^2) bits of communication.

We also obtain the tight bound of \frac{2}{\ln 2}k\pm o(k) on the communication complexity of disjointness of sets of size \le k. An asymptotic bound of \Theta(k) was previously shown by Hastad and Wigderson.