One way communication complexity of multi exact matching

Question

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.

Answer 1

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$.

Answer 2

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).