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.