ECCC-Report TR16-173https://eccc.weizmann.ac.il/report/2016/173Comments and Revisions published for TR16-173en-usTue, 19 Jun 2018 16:57:46 +0300
Revision 2
| One-sided error communication complexity of Gap Hamming Distance |
Egor Klenin,
Alexander Kozachinsky
https://eccc.weizmann.ac.il/report/2016/173#revision2Assume 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.Tue, 19 Jun 2018 16:57:46 +0300https://eccc.weizmann.ac.il/report/2016/173#revision2
Revision 1
| One-sided error communication complexity of Gap Hamming Distance |
Egor Klenin,
Alexander Kozachinsky
https://eccc.weizmann.ac.il/report/2016/173#revision1Assume 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. Fri, 02 Feb 2018 13:51:22 +0200https://eccc.weizmann.ac.il/report/2016/173#revision1
Paper TR16-173
| One-sided error communication complexity of Gap Hamming Distance |
Egor Klenin,
Alexander Kozachinsky
https://eccc.weizmann.ac.il/report/2016/173Assume 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.Sun, 06 Nov 2016 17:51:40 +0200https://eccc.weizmann.ac.il/report/2016/173