From information to exact communication
Mark Braverman, Ankit K. Garg, Denis Yu. Pankratov, Omri Weinstein · 2013
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 pm o(n) as the error tends to zero.