7
$\begingroup$

Let Alice have $n$ binary strings, each of length $n$ and let Bob have one binary string of length $n$. Bob has to output $1$ if his string matches any of Alice's exactly and $0$ otherwise.

Clearly Alice can just run $n$ copies of a randomized one-way communication protocol to send a total of $O(n\log{n})$ bits to Bob which will let him output the correct answer with good probability. Is this the best they can do?

What is the one-way randomized communication complexity, assuming private randomness, of this problem?

My guess is that this is a known problem with existing tight bounds but I have not managed to find a reference yet.

$\endgroup$
  • $\begingroup$ You could phrase this as set disjointness (well-studied) where Bob's set has size one; or set containment (don't know how well-studied in this case). $\endgroup$ – usul Oct 27 '15 at 22:19
  • $\begingroup$ Can you clarify your assumptions? Are you assuming there is a one-way channel from Alice to Bob, but no communication channel from Bob to Alice? This isn't actually stated in your question, so it would be good to make it explicit. Of course, the problem becomes trivial if there's a channel from Bob to Alice. $\endgroup$ – D.W. Oct 28 '15 at 1:16
  • $\begingroup$ @D.W. Yes this is a one-way communication complexity problem. $\endgroup$ – Lembik Oct 28 '15 at 7:48
  • $\begingroup$ @usul What results are known about set-disjointness when Bob has a set of size one? $\endgroup$ – Lembik Oct 28 '15 at 8:13
  • $\begingroup$ @Lembik, sorry I don't know. $\endgroup$ – usul Oct 29 '15 at 20:06
7
$\begingroup$

For the lower bound, consider the following problem: Alice is given $x \in \{0,1\}^n$ and Bob is given $i \in [n]$. Their goal is to output $x_i$ (in other words, they need to decide if $i$ is in the set indicated by $x$). This problem is called $INDEX$ in the literature. For the rest of this answer, I assume that Alice always speaks first.

Claim: the randomized one-way communication complexity of $INDEX$ is $\Omega(n)$. By Yao's minimax principle, it suffices to give a linear lower bound on distributional one-way communication complexity of $INDEX$ with respect to the uniform distribution. Let $\pi$ be a one-way protocol that solves $INDEX$ with probability of error $\le 1/64$ with respect to the uniform distribution. For $x \in \{0,1\}^n$ let $M_x$ denote the message sent by Alice on input $x$, and let $\pi(x,i)$ denote the protocol's output on the input $(x,i)$. We have probability of error = $\mathbb{E}_x (P_i(\pi(x,i) \neq x_i)) \le 1/64$. Thus, by Markov's inequality $P_x(P_i(\pi(x,i) \neq x_i) \ge 1/32) \le 1/2$. Let $A$ be the set of all $x$ such that $P_i(\pi(x,i) \neq x_i) \le 1/32$. Note that $|A| \ge 2^{n-1}$. Let $M$ be a message sent by Alice. Let $o \in \{0,1\}^n$ be the string defined by $o_i = \pi(M,i)$. By above, if $x$ is such that $x \in A$ and $M_x = M$, then $x$ and $o$ differ in at most $n/32$ positions. Number of such $x$ is at most ${n \choose n/32} 2^{n/32} \le (32 e)^{n/32} 2^{n/32} \le 2^{8n/32} = 2^{n/4}$. In other words, we have shown that a given message $M$ can arise out of at most $2^{n/4}$ different inputs. Thus the total number of messages has to be at least $2^{n-1}/2^{n/4} =2^{3n/4-1}$. Therefore there is a message of length at least $3n/4 -1 = \Omega(n)$.

Now, this gives an $\Omega(n)$ lower bound for your problem via a reduction. Given $x \in \{0,1\}^n$ Alice constructs $n$ strings $s_1, \ldots, s_n$ as follows: if $x_j = 1$ then Alice sets $s_j$ to be the binary expansion of $j$ (padded to have $n$ bits), otherwise she sets $s_j$ to be 0. Upon, receiving $i$, Bob constructs his own string to be the binary expansion of $i$ (padded to $n$ bits). Bob's string matches one of Alice's strings if and only if $x_i = 1$.

$\endgroup$
  • $\begingroup$ Thank you for making your answer completely self-contained. $\endgroup$ – Lembik Oct 29 '15 at 20:09
  • $\begingroup$ In the target instance, only $\log n$ out of the $n$ bits are used in the vectors being compared. With such a lot of slack in the (beautifully described) reduction, should there not be some improvement possible on $\Omega(n)$, perhaps to $\Omega(n\log n)$? $\endgroup$ – András Salamon Oct 30 '15 at 17:04
  • $\begingroup$ The other answer gives an upper bound of $O(n)$ for this problem using Bloom's filter. Although, the way it is stated it requires public randomness, but by Newman's theorem it can be changed to private randomness with at most $O(\log n)$ additive overhead. $\endgroup$ – Denis Pankratov Oct 30 '15 at 19:24
  • $\begingroup$ Thanks for clarifying. My understanding of Bloom filters was insufficiently rigorous, now have remedied this. $\endgroup$ – András Salamon Oct 30 '15 at 22:23
4
$\begingroup$

One simple approach: Use a Bloom filter. Alice can construct a Bloom filter for the set of strings she has, and then send it to Bob. The Bloom filter will have size $O(cn)$ bits, and Bob's error probability is exponentially small in $c$. In practice, you can take $c$ to be a small constant (e.g., 100).

$\endgroup$

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.