<p>Yes, because (1) <a href="https://arxiv.org/abs/1204.1505" rel="nofollow noreferrer">KLLRX</a> prove $\Omega(n)$ information lower bound for Gap Hamming (for distribution over both YES and NO inputs), and (2) Theorem 3 in <a href="http://drops.dagstuhl.de/opus/volltexte/2017/7486/" rel="nofollow noreferrer">GJPW</a> shows any such information lower bound holds also wrt distribution over NO inputs, and (3) <a href="https://ieeexplore.ieee.org/document/1181944/" rel="nofollow noreferrer">BJKS</a> paper shows that composing any function with m-bit OR increases the information complexity over NO inputs m-fold.</p>

CC BY-SA 4.0
2018-08-12T20:18:38.930Z
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.
CC BY-SA 4.0
2018-08-10T14:10:12.127Z
2018-08-10T14:10:12.127Z
Manabu Yukawa
<p>Consider the two player constant-round communication problems:</p>

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

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

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

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

<p>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). </p>

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

<communication-complexity>
Combination of Disjointness and Gap Hamming Distance communication complexity
polar_bear_cheese
# Combination of Disjointness and Gap Hamming Distance communication complexity

(Asked by: username_0 on 2018-08-07)

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)$?

**Tags:** communication-complexity

---

## 1 answers

### Answer by username_1 on 2018-08-10. Score: 3 | Accepted answer

Yes, because (1) [KLLRX](https://arxiv.org/abs/1204.1505) prove $\Omega(n)$ information lower bound for Gap Hamming (for distribution over both YES and NO inputs), and (2) Theorem 3 in [GJPW](http://drops.dagstuhl.de/opus/volltexte/2017/7486/) shows any such information lower bound holds also wrt distribution over NO inputs, and (3) [BJKS](https://ieeexplore.ieee.org/document/1181944/) paper shows that composing any function with m-bit OR increases the information complexity over NO inputs m-fold.

> **Comments:**
> **username_2**: 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?  

---

