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

CC BY-SA 3.0
2015-10-28T01:21:07.547Z
2015-10-28T01:21:07.547Z
D.W.
<p>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.</p>

<p>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)$.</p>

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

CC BY-SA 3.0
2015-10-29T20:09:09.133Z
Thank you for making your answer completely self-contained.
Simd
CC BY-SA 3.0
2015-10-30T17:04:46.103Z
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)$?
András Salamon
CC BY-SA 3.0
2015-10-30T19:24:49.777Z
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.
Denis Pankratov
CC BY-SA 3.0
2015-10-30T22:23:28.570Z
Thanks for clarifying.  My understanding of Bloom filters was insufficiently rigorous, now have remedied this.
András Salamon
CC BY-SA 3.0
2015-10-28T22:07:23.823Z
2015-10-29T02:35:18.640Z
2015-10-29T02:35:18.640Z
Denis Pankratov
<p>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.</p>

<p>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?</p>

<blockquote>
  <p>What is the one-way randomized communication complexity, assuming private randomness, of this
  problem?</p>
</blockquote>

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

CC BY-SA 3.0
2015-10-27T22:19:37.070Z
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).
usul
CC BY-SA 3.0
2015-10-28T01:16:58.913Z
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.
D.W.
CC BY-SA 3.0
2015-10-28T07:48:11.747Z
@D.W. Yes this is a one-way communication complexity problem.
Simd
CC BY-SA 3.0
2015-10-28T08:13:48.503Z
@usul What results are known about set-disjointness when Bob has a set of size one?
Simd
CC BY-SA 3.0
2015-10-29T20:06:19.647Z
@Lembik, sorry I don't know.
usul
<communication-complexity>
One way communication complexity of multi exact matching
Simd
# One way communication complexity of multi exact matching

(Asked by: username_0 on 2015-10-27)

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.

**Tags:** communication-complexity
> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_0**: @D.W. Yes this is a one-way communication complexity problem.  
> **username_0**: @usul What results are known about set-disjointness when Bob has a set of size one?  
> **username_1**: @Lembik, sorry I don't know.  

---

## 2 answers

### Answer by username_3 on 2015-10-28. Score: 7 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you for making your answer completely self-contained.  
> **username_4**: 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)$?  
> **username_3**: 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.  
> **username_4**: Thanks for clarifying.  My understanding of Bloom filters was insufficiently rigorous, now have remedied this.  

---

### Answer by username_2 on 2015-10-28. Score: 4

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


---

