Sqrt LB for set disjointness

Adapted from “The story of set disjointness” by Arkadev Chattopadhyay and Toni Pitassi.

An $Ω (\sqrt{n})$ lower bound on the randomized communication complexity of set disjointness.¹

Theorem

Let $f : 2^{[n]} \times 2^{[n]} \to {0, 1}$ be the set disjointness function: that is, given any sets $A, B \subseteq [n]$ , $f$ returns true if $A$ and $B$ are disjoint: $f (A, B) : = 1 [A \cap B = \emptyset]$ . Then the randomized² communication complexity of $f$ is $Ω (\sqrt{n})$ .³

More precisely, there is some constant probability of failure $ϵ$ such that any randomized communication protocol that succeeds with probability $\geq 1 - ϵ$ on each input must use $Ω (\sqrt{n})$ bits of communication.

Proof

Plan

By Algorithmic minimax principle, it is enough to show a distribution over inputs on which any deterministic protocol needs $Ω (\sqrt{n})$ communication in order to succed with probability $1 - ϵ$ on average. Here, we will consider the (product) distribution where both $A$ and $B$ are chosen uniformly at random in $(\binom{[n]}{\sqrt{n}})$ .

We’ll show that the corresponding $(\binom{n}{\sqrt{n}}) \times (\binom{n}{\sqrt{n}})$ communication matrix has no large “nearly $0$ -monochromatic” rectangles. That is, for any subsets $F, G \subseteq (\binom{[n]}{\sqrt{n}})$ , either

$F$ or $G$ only represents a $2^{- Ω (\sqrt{n})}$ fraction of $(\binom{[n]}{\sqrt{n}})$ ;
or a $Ω (1)$ fraction of the pairs $(A, B) \in F \times G$ intersect.

Intuitively, we want to show that if $F$ and $G$ are large, then they must both be pretty equally spread over $[n]$ , and if that’s the case, they must intersect a lot. However, there doesn’t seem to be a clean notion of “equally spread” that you can prove independently for $F$ and $G$ , so instead we’ll:

assume that and $F$ is large, and $F$ and $G$ don’t intersect much;
find a small number of sets $A$ in $F$ that cover much of $[n]$ and yet don’t intersect $G$ too much;
show that this limits the size of $G$ .

Execution

Suppose that $| F | \geq 2^{- o (\sqrt{n})} (\binom{n}{\sqrt{n}})$ , and that only an $ϵ$ fraction of the pairs $(A, B) \in F \times G$ intersect. Some sets $A \in F$ might be unusual in that they intersect with much more than an $ϵ$ fraction of the sets in $G$ , but at least half of them intersect with at most a $2 ϵ$ fraction of $G$ . Let $F^{'} \subseteq F$ be the family of such good sets; we have $| F^{'} | \geq | F | / 2 \geq 2^{- o (\sqrt{n})} (\binom{n}{\sqrt{n}})$ .

Then, find $k \leq O (\sqrt{n})$ sets $A_{1}, \dots, A_{k} \in F^{'}$ such that $| A_{1} \cup \dots \cup A_{k} | \geq n / 3$ . This is always possible given how big $F^{'}$ is: Just choose those sets greedily to increase the size of the union as quickly as possible. If at some point $| A_{1} \cup \dots \cup A_{i} | < n / 3$ and you can’t find some $A_{i + 1} \in F^{'}$ that extends the size of the union by at least $\sqrt{n} / 2$ , that would show that there are at most

\sum_{j = 0}^{\sqrt{n} / 2 - 1} \underset{inside A_{1} \cup \dots \cup A_{i}}{\underset{⏟}{(\binom{n / 3}{\sqrt{n} - j})}} \underset{outside A_{1} \cup \dots \cup A_{i}}{\underset{⏟}{(\binom{2 n / 3}{j})}} \leq O ((\binom{n / 3}{\sqrt{n} / 2}) (\binom{2 n / 3}{\sqrt{n} / 2})) \leq 2^{- Ω (\sqrt{n})} (\binom{n}{\sqrt{n}})

elements left in $F^{'}$ .

Now (using the same trick as earlier), the average set in $G$ intersects only a $2 ϵ$ fraction of the sets $A_{1}, \dots, A_{k}$ , so at least half of them intersect at most $4 k ϵ$ of them. Let $G^{'} \subseteq G$ be the family of such good sets; we have $| G^{'} | \geq | G | / 2$ .

Each set $B \in G$ can only intersect the union $A_{1} \cup \dots \cup A_{k}$ at $\leq 4 k ϵ$ points, and the rest of $B$ must lie entirely in the remaining $n - Ω (n)$ elements of $[n]$ . Therefore,

| G^{'} | \leq (\binom{k}{\leq 4 k ϵ}) (\binom{n - Ω (n)}{\sqrt{n}}) .

We can upper bound $(\binom{n - Ω (n)}{\sqrt{n}})$ by $2^{- Ω (\sqrt{n})} (\binom{n}{\sqrt{n}})$ , and by choosing $ϵ$ small enough, we can upper bound $(\binom{k}{\leq 4 k ϵ})$ by $2^{c \sqrt{n}}$ for any $c > 0$ we want, so we get

| G | \leq 2 | G^{'} | \leq 2^{- Ω (\sqrt{n})} (\binom{n}{\sqrt{n}}),

as desired.

László Babai, Péter Frankl, János Simon, “Complexity classes in communication complexity theory”. ↩
It’s very easy to prove that its deterministic communication complexity is $Ω (n)$ , see Monochromatic rectangles. ↩
We actually know that it’s $Ω (n)$ , but this is a much more complicated result. ↩