Assume that Alice has a binary string $x$ and Bob a binary string $y$, both strings are of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where $L < U$ are some integer parameters known to both parties. If the Hamming distance between $x$ and $y$ lies in the interval $(L, U)$, they are allowed to output anything. This problem is called the Gap Hamming Distance. In this paper we study public-coin one-sided error communication complexity of this problem. The error with probability at most 1/2 is allowed only for pairs at Hamming distance at least $U$. In this paper we determine this complexity up to factors logarithmic in $L$. The protocol we construct for the upper bound is simultaneous.

Minor corrections and simplifications

Assume that Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where $L < U$ are some integer parameters known to both parties. If the Hamming distance between $x$ and $y$ lies in the interval $(L, U)$, they are allowed to output anything. This problem is called the Gap Hamming Distance. In this paper we study public-coin one-sided error communication complexity of this problem. The error with probability at most 1/2 is allowed only for pairs at Hamming distance at least $U$. In this paper we establish lower bound $\Omega(L^2/U)$ for this complexity. The main result of the paper is the simultaneous protocol communicating $O((L^2/U)\log L)$ bits. Its complexity differs from the lower bound only by a $O(\log L)$ factor.

Simultaneous protocol, attaining main upper bound.

Assume that Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where $L < U$ are some integer parameters known to both parties. If the Hamming distance between $x$ and $y$ lies in the interval $(L, U)$, they are allowed to output anything. This problem is called the Gap Hamming Distance. In this paper we study public-coin one-sided error communication complexity of this problem. The error with probability at most 1/2 is allowed only for pairs at Hamming distance at least $U$. In this paper we establish the upper bound $O((L^2/U)\log L)$ and the lower bound $\Omega(L^2/U)$ for this complexity. These bounds differ only by a $O(\log L)$ factor.