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


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?

  • $\begingroup$ 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. $\endgroup$ – Clement C. Mar 4 '16 at 20:07

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.