<p>Let $C:\{0,1\}^{n} \to \{0,1\}^{2n}$ be an error correcting code with linear distance. Let $g: \{0,1\}^{n} \times \{0,1\}^{n} \to \{0,1\}$ be a function whose randomized communication complexity is large (say, $\Omega(\sqrt{n})$ or $\Omega(n))$.</p>

<p>Define $f: \{0,1\}^{2n} \times \{0,1\}^{2n} \to \{0,1,*\}$ to be the partial function that on codewords of $C$ outputs $f(x,y) = g(C^{-1}(x),C^{-1}(y))$, and it outputs $*$ if at least one of $x,y$ is not in $C$.</p>

<p>Clearly, the communication complexity of $f$ is equal to the communication complexity of $g$, and $f$ satisfies the property that for every two different inputs on which $f$ outputs 0 or 1, the distance between them is linear.</p>

CC BY-SA 3.0
2015-10-26T13:20:35.893Z
Thanks Igor. While, needless to say, the problem you describe has linear distance -- I am looking for problems in which the gap occurs naturally (is in GHD), rather than artificially (by encoding the inputs). Are there any such problems in the literature?
Anonymous
CC BY-SA 3.0
2015-10-23T13:42:07.327Z
2015-10-23T13:42:07.327Z
Igor Shinkar
<p>As mentioned in a comment above, the <a href="http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pbhm.pdf" rel="nofollow">Boolean
Hidden Matching Problem</a> introduced and studied in [BJK04,KR06] seems to (almost) meet your requirement. The input size is roughly $n\log n$ (as an input is of the form $(x,M,w)\in\{0,1\}^{2n}\times\{0,1\}^{n\times 2n}\times \{0,1\}^{2n}$, where $M$ is a very sparse matrix that can be encoded with $n\log n$ bits); and $\textsf{yes}$- and $\textsf{no}$-instances of the promise problem have distance $\Theta(n)$,</p>

<p>The one-way randomized communication complexity of $\textsf{BHM}_n$ is $\Omega(\sqrt{n})$, as shown in [KR06].</p>

<ul>
<li>[BJK04] Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity, Proceedings of ACM STOC 2004</li>
<li>[KR06] Iordanis Kerenidis, Ran Raz.
The one-way communication complexity of the Boolean Hidden Matching Problem. Electronic Colloquium on Computational Complexity (ECCC) 13(087) (2006)</li>
</ul>

CC BY-SA 3.0
2015-10-29T17:57:50.783Z
2015-10-29T17:57:50.783Z
Clement C.
<p>Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions $f:\{0,1\}^{2n} \to \{0,1,*\}$ such that the Hamming distance between every $(x,y) \in f^{-1}(1)$ and $(x',y') \in f^{-1}(0)$ is linear -- and that $f$ requires randomized protocols to communicate (say) $\Omega(\sqrt{n})$ bits?</p>

<p>(For instance, the Gap-Hamming-Distance problem has $2\sqrt{n}$ distance, whereas I'm looking for $\Omega(n)$ distance; where $GHD(x,y) = 1$ if $HD(x,y) \ge n/2 + \sqrt{n}$ and $GHD(x,y) = 1$ if $HD(x,y) \le n/2 - \sqrt{n}$.)</p>

<p><strong>Edit</strong>: As pointed out by Igor, any communication complexity predicate can be made into a problem with linear-distance by requiring the inputs to be encoded by a good code. What interests me though, is whether there exist problems in the literature, in which the linear-distance occurs in a <strong>natural</strong> way (as the distance in the Gap-Hamming-Distance problem).</p>

CC BY-SA 3.0
2015-10-28T20:55:53.280Z
Would something like the [Boolean Hidden Matching Problem](http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pbhm.pdf) fit the bill? It does require $\Omega(\sqrt{n})$ bits of communication (one-way, randomized), and it looks like it has linear distance between $\textsf{yes}$- and $\textsf{no}$-instances.
Clement C.
CC BY-SA 3.0
2015-10-28T23:58:34.367Z
(or almost linear, I guess, since the input includes the matching matrix $M$)
Clement C.
CC BY-SA 3.0
2015-10-29T05:35:09.223Z
Thanks Clement! That's precisely the kind of problems I was looking for!
Anonymous
CC BY-SA 3.0
2015-11-03T03:32:54.550Z
Another problem -- albeit in the SMP/referee model -- is basically Gap-Hamming-Distance with gap linear in $n$ (although the inputs $x,y$ have size $n\log n$ instead of $n$). See [Bavarian, Gavinsky, and Ito '15](http://arxiv.org/abs/1508.06395), more precisely Definition 1.9 and Theorem 1.8 (along with Fact 1.4): the communication complexity of $\mathsf{GapIP}_n$ in the SMP model with private randomness is $\tilde{\Omega}(\sqrt{n})$.
Clement C.
<reference-request><communication-complexity>
Communication complexity problems with linear distance
Anonymous
# Communication complexity problems with linear distance

(Asked by: username_0 on 2015-08-24)

Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions $f:\{0,1\}^{2n} \to \{0,1,\*\}$ such that the Hamming distance between every $(x,y) \in f^{-1}(1)$ and $(x',y') \in f^{-1}(0)$ is linear -- and that $f$ requires randomized protocols to communicate (say) $\Omega(\sqrt{n})$ bits?

(For instance, the Gap-Hamming-Distance problem has $2\sqrt{n}$ distance, whereas I'm looking for $\Omega(n)$ distance; where $GHD(x,y) = 1$ if $HD(x,y) \ge n/2 + \sqrt{n}$ and $GHD(x,y) = 1$ if $HD(x,y) \le n/2 - \sqrt{n}$.)

**Edit**: As pointed out by Igor, any communication complexity predicate can be made into a problem with linear-distance by requiring the inputs to be encoded by a good code. What interests me though, is whether there exist problems in the literature, in which the linear-distance occurs in a **natural** way (as the distance in the Gap-Hamming-Distance problem).

**Tags:** reference-request, communication-complexity
> **Comments:**
> **username_1**: Would something like the [Boolean Hidden Matching Problem](http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pbhm.pdf) fit the bill? It does require $\Omega(\sqrt{n})$ bits of communication (one-way, randomized), and it looks like it has linear distance between $\textsf{yes}$- and $\textsf{no}$-instances.  
> **username_1**: (or almost linear, I guess, since the input includes the matching matrix $M$)  
> **username_0**: Thanks Clement! That's precisely the kind of problems I was looking for!  
> **username_1**: Another problem -- albeit in the SMP/referee model -- is basically Gap-Hamming-Distance with gap linear in $n$ (although the inputs $x,y$ have size $n\log n$ instead of $n$). See [Bavarian, Gavinsky, and Ito '15](http://arxiv.org/abs/1508.06395), more precisely Definition 1.9 and Theorem 1.8 (along with Fact 1.4): the communication complexity of $\mathsf{GapIP}_n$ in the SMP model with private randomness is $\tilde{\Omega}(\sqrt{n})$.  

---

## 2 answers

### Answer by username_2 on 2015-10-23. Score: 6

Let $C:\{0,1\}^{n} \to \{0,1\}^{2n}$ be an error correcting code with linear distance. Let $g: \{0,1\}^{n} \times \{0,1\}^{n} \to \{0,1\}$ be a function whose randomized communication complexity is large (say, $\Omega(\sqrt{n})$ or $\Omega(n))$.

Define $f: \{0,1\}^{2n} \times \{0,1\}^{2n} \to \{0,1,\*\}$ to be the partial function that on codewords of $C$ outputs $f(x,y) = g(C^{-1}(x),C^{-1}(y))$, and it outputs $\*$ if at least one of $x,y$ is not in $C$.

Clearly, the communication complexity of $f$ is equal to the communication complexity of $g$, and $f$ satisfies the property that for every two different inputs on which $f$ outputs 0 or 1, the distance between them is linear.

> **Comments:**
> **username_0**: Thanks Igor. While, needless to say, the problem you describe has linear distance -- I am looking for problems in which the gap occurs naturally (is in GHD), rather than artificially (by encoding the inputs). Are there any such problems in the literature?  

---

### Answer by username_1 on 2015-10-29. Score: 2

As mentioned in a comment above, the [Boolean
Hidden Matching Problem](http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pbhm.pdf) introduced and studied in [BJK04,KR06] seems to (almost) meet your requirement. The input size is roughly $n\log n$ (as an input is of the form $(x,M,w)\in\{0,1\}^{2n}\times\{0,1\}^{n\times 2n}\times \{0,1\}^{2n}$, where $M$ is a very sparse matrix that can be encoded with $n\log n$ bits); and $\textsf{yes}$- and $\textsf{no}$-instances of the promise problem have distance $\Theta(n)$,

The one-way randomized communication complexity of $\textsf{BHM}\_n$ is $\Omega(\sqrt{n})$, as shown in [KR06].

* [BJK04] Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity, Proceedings of ACM STOC 2004
* [KR06] Iordanis Kerenidis, Ran Raz.
  The one-way communication complexity of the Boolean Hidden Matching Problem. Electronic Colloquium on Computational Complexity (ECCC) 13(087) (2006)


---

