Some Bounds on Communication Complexity of Gap Hamming Distance

Alexander Kozachinskiy

In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (${\mathsf{GHD}}_{L,U}^n$): Alice and Bob are given binary string of length $n$ and t…