Alexander A. Sherstov

In the gap Hamming distance problem, two parties must

determine whether their respective strings $x,y\in\{0,1\}^n$

are at Hamming distance less than $n/2-\sqrt n$ or greater

than $n/2+\sqrt n.$ In a recent tour de force, Chakrabarti and

Regev (STOC '11) proved the long-conjectured $\Omega(n)$ bound

on the randomized communication ...
more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform ... more >>>