# Combination of Disjointness and Gap Hamming Distance communication complexity

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.
• 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? Aug 12 '18 at 20:18