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:1511.08854

Some Bounds on Communication Complexity of Gap Hamming Distance

Alexander Kozachinskiy

Published Nov 27, 2015• 1 citation
arXivHTMLPDF

Abstract

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|$.

DOI
10.48550/arxiv.1511.08854

Related papers

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

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

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where$0\leqslant r < R\leqslant n$are given integers and Alice and Bob need to determine whether their respective matrices$A, B\in \mathbb{F}^{n\times n}$satisfy rk$(A+B)=r$versus rk$(A+B)=R$. We show that this problem has commu-nication cost$\Omega(r^{2}\log\vert \mathbb{F}\vert)$, which is optimal. Our lower bound holds even for quantum protocols and even for error probability$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$, which too is optimal because this problem has a two-bit classical protocol with error$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers$r$and$R$, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace$S$, Bob has a subspace$T$) and they need to approximate the dimension of the subspace$S+T$generated by$S$and$T$(equivalently, approximate the dimension of$S\cap T$). As an application, we obtain an$\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$memory lower bound for any streaming algorithm with$k$passes that approximates the rank of an input matrix$M\in \mathbb{F}^{n\times n}$within a factor of$\sqrt{2}-\delta$, for any$\delta > 0$. Our result is an exponential improvement in$k$over previous work.

arXiv:2410.20094•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•1 citation

Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays +2 more

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I)and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.

arXiv:1204.1505•Annual Symposium on Foundations of Computer Science•Oct 1, 2012•51 citations

A Block-Sensitivity Lower Bound for Quantum Testing Hamming Distance

Marcos Villagra

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|\geq 1$ and $a$ and $b$ could depend on $n$. In this short note, we give a lower bound of $Ω( \sqrt{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.

arXiv:1705.09710•May 26, 2017•0 citations

Communication Memento: Memoryless Communication Complexity

Srinivasan Arunachalam, Supartha Podder

We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].

Conference on Innovations in Theoretical Computer Science•Jan 1, 2021•1 citation
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.
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.
We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where0⩽r<R⩽n0\leqslant r < R\leqslant n0⩽r<R⩽nare given integers and Alice and Bob need to determine whether their respective matricesA,B∈Fn×nA, B\in \mathbb{F}^{n\times n}A,B∈Fn×nsatisfy rk(A+B)=r(A+B)=r(A+B)=rversus rk(A+B)=R(A+B)=R(A+B)=R. We show that this problem has commu-nication costΩ(r2log⁡∣F∣)\Omega(r^{2}\log\vert \mathbb{F}\vert)Ω(r2log∣F∣), which is optimal. Our lower bound holds even for quantum protocols and even for error probability12(1−∣F∣−r/3)\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})21​(1−∣F∣−r/3), which too is optimal because this problem has a two-bit classical protocol with error12(1−∣F∣−Θ(r))\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})21​(1−∣F∣−Θ(r)). Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integersrrrandRRR, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspaceSSS, Bob has a subspaceTTT) and they need to approximate the dimension of the subspaceS+TS+TS+Tgenerated bySSSandTTT(equivalently, approximate the dimension ofS∩TS\cap TS∩T). As an application, we obtain anΩ(n2log⁡∣F∣)/k\Omega(n^{2}\log\vert \mathbb{F}\vert)/kΩ(n2log∣F∣)/kmemory lower bound for any streaming algorithm withkkkpasses that approximates the rank of an input matrixM∈Fn×nM\in \mathbb{F}^{n\times n}M∈Fn×nwithin a factor of2−δ\sqrt{2}-\delta2​−δ, for anyδ>0\delta > 0δ>0. Our result is an exponential improvement inkkkover previous work.
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I)and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance hhh between two strings of length nnn is greater than aaa or less than bbb, where the gap g=∣a−b∣≥1g=|a-b|\geq 1g=∣a−b∣≥1 and aaa and bbb could depend on nnn. In this short note, we give a lower bound of Ω(n/g)Ω( \sqrt{n/g})Ω(n/g​) on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght nnn. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.
We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].