<p>If A has a pointer (of length $\log n$) to a bit of B (whose input has length $n$), that requires, $\Theta(\log n)$ one-way communication, even with a public-coin. On the other hand, the referee needs $\Theta(n)$ bits to solve the problem, even with a public-coin. Or did I misunderstand something?</p>

CC BY-SA 3.0
2016-03-04T20:07:06.660Z
No, that's a perfectly good example (thanks!). I reckon the inherent asymmetricity of the problem is the key here -- just swapping Alice and Bob's roles would make it $\Theta(n)$ in the one-way randomized setting as well.
Clement C.
CC BY-SA 3.0
2016-03-04T18:38:10.777Z
2016-03-04T18:38:10.777Z
domotorp
<p>In the referee (SMP: Simultaneous Message Passing) model introduced by Yao (see e.g. [1]), Alice and Bob have respectively inputs $x\in X$ and $y\in Y$, and wish to communicate with a third-party, the Referee, to compute $f(x,y)$ where $f\colon X\times Y\to\{0,1\}$ is a function known to the three parties.</p>

<p>The restriction, however, is that the communication is one-way: Alice and Bob can only send a message to the referee, who then must output the answer ($A\leadsto R$ and $B\leadsto R$). (This differs from the one-way CC setting as the referee does not hold any input.)</p>

<p>While the deterministic communication complexity in this model seems well-understood, and lower bounds (tight for $\sf EQ_n$) for the private-coin setting are known [1], I could not find examples of cases (preferably for promise problems, i.e. with a gap between $\sf yes$ and $\sf no$-instances) for which there was a strong separation between one-way <em>public-coin</em> communication complexity and SMP <em>public-coin</em> communication complexity.</p>

<blockquote>
  <p>What are problems $\Pi$ for which there is a gap between $\operatorname{ow-CC}_{\rm pub}(\Pi)$ and $\operatorname{smp-CC}_{\rm pub}(\Pi)$?</p>
</blockquote>

<p>For instance, ${\sf EQ}_n$ is $\Theta(\sqrt{n})$ for SMP private-coin, and $O(\log {n})$ for one-way private-coin; but in the public-coin setting, it is $O(1)$ for both. On the other end of the spectrum, ${\sf DISJ}_n$ is $\Theta({n})$ for both models, and so is ${\sf GAPHAMMING}_n$.</p>

<p>(As a side note, one can derive a separation between one-way <em>"imperfectly-shared"-coin</em> communication complexity and SMP <em>"imperfectly-shared"-coin</em> communication from the work of Bavarian et al. [2] on communication with correlated random bits, from their ${\sf GAPIP}_n$ problem, but this separation does not hold for perfectly shared randomness (public coins)).</p>

<p>[1] <em>Randomized simultaneous messages: solution of a problem of Yao in communication complexity</em>, L. Babai. 1997.
<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=612319&amp;tag=1" rel="noreferrer">http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=612319&amp;tag=1</a></p>

<p>[2] <em>On the Role of Shared Randomness in Simultaneous Communication,</em> M. Bavarian, D. Gavinsky, T. Ito, 2014.
<a href="http://arxiv.org/abs/1508.06395" rel="noreferrer">http://arxiv.org/abs/1508.06395</a></p>

<reference-request><communication-complexity>
Problems still "hard" in the SMP/Referee model with shared randomness?
Clement C.
# Problems still "hard" in the SMP/Referee model with shared randomness?

(Asked by: username_0 on 2016-03-04)

In the referee (SMP: Simultaneous Message Passing) model introduced by Yao (see e.g. [1]), Alice and Bob have respectively inputs $x\in X$ and $y\in Y$, and wish to communicate with a third-party, the Referee, to compute $f(x,y)$ where $f\colon X\times Y\to\{0,1\}$ is a function known to the three parties.

The restriction, however, is that the communication is one-way: Alice and Bob can only send a message to the referee, who then must output the answer ($A\leadsto R$ and $B\leadsto R$). (This differs from the one-way CC setting as the referee does not hold any input.)

While the deterministic communication complexity in this model seems well-understood, and lower bounds (tight for $\sf EQ\_n$) for the private-coin setting are known [1], I could not find examples of cases (preferably for promise problems, i.e. with a gap between $\sf yes$ and $\sf no$-instances) for which there was a strong separation between one-way *public-coin* communication complexity and SMP *public-coin* communication complexity.

> What are problems $\Pi$ for which there is a gap between $\operatorname{ow-CC}\_{\rm pub}(\Pi)$ and $\operatorname{smp-CC}\_{\rm pub}(\Pi)$?

For instance, ${\sf EQ}\_n$ is $\Theta(\sqrt{n})$ for SMP private-coin, and $O(\log {n})$ for one-way private-coin; but in the public-coin setting, it is $O(1)$ for both. On the other end of the spectrum, ${\sf DISJ}\_n$ is $\Theta({n})$ for both models, and so is ${\sf GAPHAMMING}\_n$.

(As a side note, one can derive a separation between one-way *"imperfectly-shared"-coin* communication complexity and SMP *"imperfectly-shared"-coin* communication from the work of Bavarian et al. [2] on communication with correlated random bits, from their ${\sf GAPIP}\_n$ problem, but this separation does not hold for perfectly shared randomness (public coins)).

[1] *Randomized simultaneous messages: solution of a problem of Yao in communication complexity*, L. Babai. 1997.
<http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=612319&tag=1>

[2] *On the Role of Shared Randomness in Simultaneous Communication,* M. Bavarian, D. Gavinsky, T. Ito, 2014.
<http://arxiv.org/abs/1508.06395>

**Tags:** reference-request, communication-complexity

---

## 1 answers

### Answer by username_1 on 2016-03-04. Score: 2

If A has a pointer (of length $\log n$) to a bit of B (whose input has length $n$), that requires, $\Theta(\log n)$ one-way communication, even with a public-coin. On the other hand, the referee needs $\Theta(n)$ bits to solve the problem, even with a public-coin. Or did I misunderstand something?

> **Comments:**
> **username_0**: No, that's a perfectly good example (thanks!). I reckon the inherent asymmetricity of the problem is the key here -- just swapping Alice and Bob's roles would make it $\Theta(n)$ in the one-way randomized setting as well.  

---

