Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-173 | 19th June 2018 16:57

One-sided error communication complexity of Gap Hamming Distance

RSS-Feed




Revision #2
Authors: Egor Klenin, Alexander Kozachinsky
Accepted on: 19th June 2018 16:57
Downloads: 752
Keywords: 


Abstract:

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.



Changes to previous version:

Minor corrections and simplifications


Revision #1 to TR16-173 | 2nd February 2018 13:51

One-sided error communication complexity of Gap Hamming Distance





Revision #1
Authors: Egor Klenin, Alexander Kozachinsky
Accepted on: 2nd February 2018 13:51
Downloads: 611
Keywords: 


Abstract:

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.



Changes to previous version:

Simultaneous protocol, attaining main upper bound.


Paper:

TR16-173 | 5th November 2016 22:59

One-sided error communication complexity of Gap Hamming Distance





TR16-173
Authors: Egor Klenin, Alexander Kozachinsky
Publication: 6th November 2016 17:51
Downloads: 1475
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint