8
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    Oct 28, 2015 at 20:55
  • $\begingroup$ (or almost linear, I guess, since the input includes the matching matrix $M$) $\endgroup$
    – Clement C.
    Oct 28, 2015 at 23:58
  • $\begingroup$ Thanks Clement! That's precisely the kind of problems I was looking for! $\endgroup$
    – Anonymous
    Oct 29, 2015 at 5:35
  • $\begingroup$ 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})$. $\endgroup$
    – Clement C.
    Nov 3, 2015 at 3:32

2 Answers 2

Reset to default
6
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Anonymous
    Oct 26, 2015 at 13:20
2
$\begingroup$

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)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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