# Communication complexity problems with linear distance

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

• Would something like the Boolean Hidden Matching Problem 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. Oct 28 '15 at 20:55
• (or almost linear, I guess, since the input includes the matching matrix $M$) – Clement C. Oct 28 '15 at 23:58
• Thanks Clement! That's precisely the kind of problems I was looking for! – Anonymous Oct 29 '15 at 5:35
• 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, 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. Nov 3 '15 at 3:32

## 2 Answers

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.

• 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 Oct 26 '15 at 13:20

As mentioned in a comment above, the Boolean Hidden Matching Problem 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)