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:quant-ph/0509181 · Information Processing Letters

The communication complexity of the Hamming distance problem

Wei Huang, Yaoyun Shi, Shengyu Zhang, Yufan Zhu

Published Jun 1, 2006• 62 citations
arXivHTMLPDF
DOI
10.1016/j.ipl.2006.01.014

Related papers

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

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

Lecture notes in computer science•Jan 1, 2006•1 citation

The Communication Complexity of the Exact Gap-Hamming Problem.

Anup Rao, Amir Yehudayoff

Electronic colloquium on computational complexity•Jan 1, 2020•1 citation

Secure Hamming Distance Based Computation and Its Applications

Ayman Jarrous, Benny Pinkas B

Lecture notes in computer science•Jan 1, 2009•70 citations

Two quantum protocols for secure hamming distance computation

Zhenwan Peng, Runhua Shi, Pan-hong Wang +1 more

Quantum Information Processing•Dec 5, 2018•7 citations

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

The Communication Complexity of Gap Hamming Distance.

Alexander A. Sherstov

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.

Electronic colloquium on computational complexity•Jan 1, 2011•9 citations
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.