In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem ( $\mathsf{GHD}^n_{L, U}$ ): Alice and Bob are given binary string of length $n$ and they are guaranteed that Hamming distance between their inputs is either $\le L$ or $\ge U$ for some $L < U$ . They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of $\mathsf{GHD}^n_{L, U}$ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates $O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)$ bits and has one-sided error probability $e^{-s}$ provided $s \ge \frac{(L + \frac{10}{n})^3}{U^2}$ . Our second result is about deterministic communication complexity of $\mathsf{GHD}^n_{0,\, t}$ . Surprisingly, it can be computed with logarithmic precision: $\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),$ where $V_2(n, r)$ denotes the size of Hamming ball of radius $r$ . As an application of this result for every $c < 2$ we prove a $Ω\left(\frac{n(2 - c)^2}{p}\right)$ lower bound on the space complexity of any $c$ -approximate deterministic $p$ -pass streaming algorithm for computing the number of distinct elements in a data stream of length $n$ with tokens drawn from the universe $U = \{1, 2, \ldots, n\}$ . Previously that lower bound was known for $c < \frac{3}{2}$ and for $c < 2$ but with larger $|U|$ .In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem ($\mathsf{GHD}^n_{L, U}$): Alice and Bob are given binary string of length $n$ and they are guaranteed that Hamming distance between their inputs is either $\le L$ or $\ge U$ for some $L < U$. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of $\mathsf{GHD}^n_{L, U}$ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates $O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)$ bits and has one-sided error probability $e^{-s}$ provided $s \ge \frac{(L + \frac{10}{n})^3}{U^2}$. Our second result is about deterministic communication complexity of $\mathsf{GHD}^n_{0,\, t}$. Surprisingly, it can be computed with logarithmic precision: $$\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),$$ where $V_2(n, r)$ denotes the size of Hamming ball of radius $r$. As an application of this result for every $c < 2$ we prove a $Ω\left(\frac{n(2 - c)^2}{p}\right)$ lower bound on the space complexity of any $c$-approximate deterministic $p$-pass streaming algorithm for computing the number of distinct elements in a data stream of length $n$ with tokens drawn from the universe $U = \{1, 2, \ldots, n\}$. Previously that lower bound was known for $c < \frac{3}{2}$ and for $c < 2$ but with larger $|U|$.

arXiv:1511.08854Nov 27, 20151 citation

Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance

Andris Ambainis, William I. Gasarch, Aravind Srinavasan +1 more

Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by lower-bounding the ranks of the appropriate matrices.Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by lower-bounding the ranks of the appropriate matrices.

arXiv:cs/0411076Nov 20, 20042 citations

Lower bounds for one-way probabilistic communication complexity

Farid Mansurovich Ablayev

Lecture notes in computer scienceJan 1, 199315 citations

Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems

Andris Ambainis, William I. Gasarch, Aravind Srinivasan +1 more

Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.

ACM Transactions on Computation TheoryJun 26, 20156 citations

The Communication Complexity of the Exact Gap-Hamming Problem.

Anup Rao, Amir Yehudayoff

Electronic colloquium on computational complexityJan 1, 20200 citations

In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (

\mathsf{GHD}^n_{L, U}

): Alice and Bob are given binary string of length

n

and they are guaranteed that Hamming distance between their inputs is either

\le L

\ge U

for some

L < U

. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of

\mathsf{GHD}^n_{L, U}

for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates

O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)

bits and has one-sided error probability

e^{-s}

provided

s \ge \frac{(L + \frac{10}{n})^3}{U^2}

. Our second result is about deterministic communication complexity of

\mathsf{GHD}^n_{0,\, t}

. Surprisingly, it can be computed with logarithmic precision:

\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),

where

V_2(n, r)

denotes the size of Hamming ball of radius

r

. As an application of this result for every

c < 2

we prove a

Ω\left(\frac{n(2 - c)^2}{p}\right)

lower bound on the space complexity of any

c

-approximate deterministic

p

-pass streaming algorithm for computing the number of distinct elements in a data stream of length

n

with tokens drawn from the universe

U = \{1, 2, \ldots, n\}

. Previously that lower bound was known for

c < \frac{3}{2}

and for

c < 2

but with larger

|U|