In the gap Hamming distance problem, two parties must determine whether their respective strings x,y ∈ {0,1} n are at Hamming distance less than n/2 − √ n or greater than n/2 + √ n. In a recent tour de force, Chakrabarti and Regev (2010) proved the long-conjectured Ω(n) lower bound on the randomized communication complexity of this problem. In follow-up work, Vidick (2010) discovered a simpler proof. We contribute a new proof, which is simpler yet and a page-and-a-half long.
In the gap Hamming distance problem, two parties must determine whether their respective strings x,y ∈ {0,1} n are at Hamming distance less than n/2 − √ n or greater than n/2 + √ n. In a recent tour de force, Chakrabarti and Regev (2010) proved the long-conjectured Ω(n) lower bound on the randomized communication complexity of this problem. In follow-up work, Vidick (2010) discovered a simpler proof. We contribute a new proof, which is simpler yet and a page-and-a-half long.
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance h between two strings of length n is greater than a or less than b, where the gap g=∣a−b∣≥1 and a and b could depend on n. In this short note, we give a lower bound of Ω(n/g) on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght n. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.
In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (GHDL,Un): Alice and Bob are given binary string of length n and they are guaranteed that Hamming distance between their inputs is either ≤L or ≥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 GHDL,Un for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates O((Us)31⋅nlogn) bits and has one-sided error probability e−s provided s≥U2(L+n10)3. Our second result is about deterministic communication complexity of GHD0,tn. Surprisingly, it can be computed with logarithmic precision: D(GHD0,tn)=n−log2V2(n,⌊2t⌋)+O(logn), where V2(n,r) denotes the size of Hamming ball of radius r. As an application of this result for every c<2 we prove a Ω(pn(2−c)2) 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,…,n}. Previously that lower bound was known for c<23 and for c<2 but with larger ∣U∣.
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.
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 at most a bits? Let 0 ≤ a ≤ 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 employing basic tools from combinatorics and calculus to lower-bound 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.