Exact communication bounds for disjointness
Ankit Garg
March 19, 2014
We determine the exact communication complexity of disjointness up to low order terms in the near zero-error regime. This is done by computing the exact zero-error information complexity of the 2-bit AND function. Towards this end, we develop a new local characterization of the zero-error information complexity function for two party communication problems.
Joint work with Mark Braverman, Denis Pankratov and Omri Weinstein.