# Problems still “hard” in the SMP/Referee model with shared randomness?

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

## 1 Answer

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?

• 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. Mar 4 '16 at 20:07