2
$\begingroup$

This was a challenge problem I read some time ago and just remembered it:

Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect sets $S_A$ and $S_B$ such that $|S_A \cup S_B| = n-k$ where $k\leq \sqrt n$. There is no guarantee in what order any of these will be collected in by each person. The goal is for $A$ to send $B$ a short message of bits so that $B$ can infer (at least) ONE of the $k$ objects missing from the union of their sets, i.e., $$k \in \{1,\ldots,n\} \setminus (S_A \cup S_B).$$ The protocol or composition of the message is agreed upon before hand, but since neither of them know the value of $k$ a priori the message can't be based on that. Before entering the maze, both parties have access to shared randomness or a set of random bits they know and can be used to communicate later (i.e., an adversarial maze generator does not have access to this randomness). (I am not sure if this detail changes the problem.)

We know $k \geq 1$ and the sets $S_A$ and $S_B$ are disjoint.

$A$ can of course base his answer on $S_A$ but can't transmit all of $S_A$. For example I came up with: if $A$ sends the sum of the elements of $S_A$ and the size of $S_A$, then $B$ can always infer if only one element is missing ($k=1$) but will fail otherwise. This takes $O(\log n)$ bits.

But how can we design a protocol to achieve the following:

$A$ sends a message with $O(\log^3 n)$ bits such that $B$ with probability $1-\frac{1}{n^c}$ can infer (at least) ONE missing object for any $1 \leq k \leq \sqrt n$ (and with remaining probability fails), where $c$ is some number given ahead of time (i.e., it is not under the control of or chosen by $A$ but the constant factor of $O(\log^3 n)$ can depend on it).

To clarify, the goal is to design a message protocol that will achieve the desired result for any values of $n$ and $c$. So the program itself can't pick the value of $c$.

$\endgroup$
  • $\begingroup$ This question seems to be going completely unanswered! I guess it has stumped a lot of people! I guess that is why they call it a challenge problem... :) $\endgroup$ – Four_FUN Nov 18 '14 at 7:49
  • $\begingroup$ Patience, young Padawan. $\endgroup$ – Raphael Nov 19 '14 at 17:38
  • $\begingroup$ To be clear, we don't know anything about "fairness" here? In particular, $S_A = \emptyset$ is a distinct possibility? By $\log^3 n$ we mean $(\log n)^3$ here? $\endgroup$ – Raphael Nov 19 '14 at 18:04
  • $\begingroup$ Both of those statements are indeed correct. I am very patient. I just like to make observational jokes! :) $\endgroup$ – Four_FUN Nov 21 '14 at 2:06

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.