Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:cs/0411076

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

Andris Ambainis, William I. Gasarch, Aravind Srinavasan, Andrey Utis

Published Nov 20, 2004• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.cs/0411076

Related papers

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.

ACM Transactions on Computation Theory•Jun 26, 2015•6 citations

Lower bounds on the Deterministic and Quantum Communication Complexities 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 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.

•Apr 1, 2008•0 citations

Lower bounds on the Deterministic and Quantum Communication Complexity of HAM n a

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 theydiffer on at most a bits? Let 0 < = a < = n- 1. We show that any deterministic protocol, as wellas any error-free quantum protocol ( C * version), for this problem requires at least n- 2 bits ofcommunication. 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.

Electronic colloquium on computational complexity•Jan 1, 2004•0 citations

Some Bounds on Communication Complexity of Gap Hamming Distance

Alexander Kozachinskiy

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.08854•Nov 27, 2015•1 citation

One-Sided Error Communication Complexity of Gap Hamming Distance

Egor Klenin, Alexander Kozachinskiy

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.

Leibniz international proceedings in informatics•Jan 1, 2018•0 citations

New bounds on the classical and quantum communication complexity of some graph properties

Gábor Ivanyos, Hartmut Klauck, Troy Lee +2 more

We study the communication complexity of a number of graph properties where the edges of the graph $G$ are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.

arXiv:1204.4596•Leibniz international proceedings in informatics•Jan 1, 2012•11 citations
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 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 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 theydiffer on at most a bits? Let 0 < = a < = n- 1. We show that any deterministic protocol, as wellas any error-free quantum protocol ( C * version), for this problem requires at least n- 2 bits ofcommunication. 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.
In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (GHDL,Un\mathsf{GHD}^n_{L, U}GHDL,Un​): Alice and Bob are given binary string of length nnn and they are guaranteed that Hamming distance between their inputs is either ≤L\le L≤L or ≥U\ge U≥U for some L<UL < UL<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\mathsf{GHD}^n_{L, U}GHDL,Un​ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates O((sU)13⋅nlog⁡n)O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)O((Us​)31​⋅nlogn) bits and has one-sided error probability e−se^{-s}e−s provided s≥(L+10n)3U2s \ge \frac{(L + \frac{10}{n})^3}{U^2}s≥U2(L+n10​)3​. Our second result is about deterministic communication complexity of GHD0, tn\mathsf{GHD}^n_{0,\, t}GHD0,tn​. Surprisingly, it can be computed with logarithmic precision: D(GHD0, tn)=n−log⁡2V2(n,⌊t2⌋)+O(log⁡n),\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),D(GHD0,tn​)=n−log2​V2​(n,⌊2t​⌋)+O(logn), where V2(n,r)V_2(n, r)V2​(n,r) denotes the size of Hamming ball of radius rrr. As an application of this result for every c<2c < 2c<2 we prove a Ω(n(2−c)2p)Ω\left(\frac{n(2 - c)^2}{p}\right)Ω(pn(2−c)2​) lower bound on the space complexity of any ccc-approximate deterministic ppp-pass streaming algorithm for computing the number of distinct elements in a data stream of length nnn with tokens drawn from the universe U={1,2,…,n}U = \{1, 2, \ldots, n\}U={1,2,…,n}. Previously that lower bound was known for c<32c < \frac{3}{2}c<23​ and for c<2c < 2c<2 but with larger ∣U∣|U|∣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.
We study the communication complexity of a number of graph properties where the edges of the graph GGG are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.