Let $X_m=[m]=\{0,1,\dots,m-1\}$ and let $Y_m=[2m]\setminus [m]$. Given is a complete bipartite graph $G_m$, with parts $X_m$ and $Y_m$ and edges $\{x,y\}$ for every $x\in X_m$ and $y\in Y_m$. Alice and Bob are given subsets $A$ and $B$ of $[2m]$, with $|A|=a$ and $|B|=b$, and further these subsets are small relative to $m$, in the sense that $a < b \le m$. For convenience, let $C = A\cup B$. The parties must agree on a common pair of vertices $u\in X_m$ and $v\in Y_m$, that represent some edge of $G_m$ that is not in the subgraph induced by $C$, in other words so that either $u \not\in C$ or $v\not\in C$.

Is this game known, and is there a good lower bound on the amount of communication required?

The size condition guarantees that the decision version is trivial (Alice sends "YES" to Bob): since $|C|<2m$ there is always some vertex that is not held by either party, so it together with any vertex in the other part forms a non-edge of $G_m[C]$. Since $a$ is small relative to $m$, Alice can send a description of $A$ to Bob using $\lceil\lg\binom{2m}{a}\rceil = O(a\lg m)$ bits. Furthermore, Alice sending a random element from $X\setminus A$ and one from $Y\setminus A$ gives a randomized one-way protocol with vanishing error (at least in some parameter regimes) and cost $O(\lg m)$. In contrast, a set disjointness lower bound applied to the complements of $A$ and $B$ would predict $\Omega(m)$ bits being required, contradicting the trivial upper bound, so a straightforward reduction from set disjointness does not work (of course, a less direct reduction might work). The implicit description of edges seems to be introducing an ingredient that I do not recognise from the usual communication games.

  • $\begingroup$ I don't completely understand your question. Is the goal to agree on a common pair $(u,v)$? Isn't this equivalent to playing the game of agreeing on some $u\in X\setminus (A\cup B)$ twice (in parallel) with the only thing connecting the two copies of the game being the size restrictions? I also don't understand your remarks that follow the question. $\endgroup$ – domotorp Dec 20 '16 at 14:14
  • $\begingroup$ I do not really understand why you need a graph in this ... I still do not understand why Alice can say yes. Indeed, you allow $b = m$. Thus, you can have $B = Y_m$. In this case, you cannot find the desired $(u,v)$ as you want $v \in Y \setminus (A \cup B) = \emptyset$... Even if you have $b < m$, you still may have $A \cup B \supset Y$. Please clarify. $\endgroup$ – holf Dec 20 '16 at 15:27
  • $\begingroup$ @domotorp, thanks for your helpful comments. I have updated the question. It seems the hard part here was formulating the question precisely enough; once it is set out clearly then the answer seems straightforward. Perhaps you would like to turn your second sentence into an answer, so that I could accept it? $\endgroup$ – András Salamon Dec 20 '16 at 16:22
  • $\begingroup$ @holf: you are right, this doesn't seem to rely on a graph when formulated correctly. $\endgroup$ – András Salamon Dec 20 '16 at 16:23
  • 2
    $\begingroup$ Now the question seems to have changed, at least I thought earlier that both $u$ and $v$ had to be outside $C$, but now only one of them has to be. I'm still not entirely sure what kind of answer you're looking for, but this might be of your interest: arxiv.org/abs/1304.1217 $\endgroup$ – domotorp Dec 20 '16 at 19:43

Your Answer

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

Browse other questions tagged or ask your own question.