Consider the two player constant-round communication problems:

Gap Hamming Distance $\Delta(a,b)$ where Alice and Bob each has an $n$-length bit string $a$ and $b$ respectively.

YES case: $\Delta(a,b) \geq n/2+\sqrt{n}$.

NO case: $\Delta(a,b) \leq n/2-\sqrt{n}$.

Known result: Distinguishing between YES and NO requires $\Omega(n)$ bits of communication

Consider $m$ instances of Gap Hamming Distance $a_i,b_i$ for $i=1,2,\ldots,m$. Alice has $a_i$ and Bob has $b_i$. We are promised such that either all $(a_i,b_i)$ are NO instance (Case 1). Or exactly one pair of $(a_i,b_i)$ is a YES instance (Case 2).

Is is true that the communication complexity to distinguish Case 1 and Case 2 of this new problem is $\Omega(mn)$?

Yes, because (1) KLLRX prove $\Omega(n)$ information lower bound for Gap Hamming (for distribution over both YES and NO inputs), and (2) Theorem 3 in GJPW shows any such information lower bound holds also wrt distribution over NO inputs, and (3) BJKS paper shows that composing any function with m-bit OR increases the information complexity over NO inputs m-fold.

  • 1
    To make sure I parse this correctly: this implies communication complexity $\Omega(mn)$ for arbitrary number of rounds (not necessarily constant), and even for "at least one pair is a $\textsf{yes}$ instance" as $\textsf{yes}$ instances (i.e., dropping the promise "exactly one)—is that right? – Clement C. Aug 12 at 20:18
  • There is also a related easier question for one-round lower bound. Suppose Alice has $a_1,\ldots,a_m$ each of length $n$. Bob has $b$ of length $n$ and an index $i$. Bob wants to output the answer for standard $GHD(a_i,b)$. It should be obvious that this requires $\Omega(mn)$ bits of communication? – HTV 4 mins ago

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.