C1: Lower Bounds for Set Disjointness (for product distribution)

March 20, 2024

• Input
• Theorem 1
• Proof of Theorem 1
• Reference

Attention: there is a mistake in the reference.

Input

Consider such a product distribution $\mu$ on inputs: we sample $S, T$ independently and uniformly at random from the set of all subsets of $[n]$ that have cardinality $\lfloor \sqrt{n} \rfloor$.

Theorem 1

$\textbf{Theorem 1} (\text{Babai, Frankl, and Simon})$ Given the above $\mu, S, T$, we obtain the deterministic communication complexity $D^\mu_\epsilon (\textsf{DISJ}) =\Omega(\sqrt{n})$.

Proof of Theorem 1

Most of the proof is based on corruption bound.

$\textbf{Theorem 2}$. Let $f: X\times Y \to \{0,1\}$ be a function, and let $\alpha,\beta > 0$ be some parameters. Given $\mu$ that is a probability distribution on $X \times Y$ such that every rectangle $R$ has $\mu(R \cap f^{-1}(0)) \geq \alpha \mu(R) - \beta.$ Then, for all $\epsilon > 0$,

$$R_\epsilon \geq \log_2 \big((\alpha \mu(f^{-1}(1)) -\epsilon)/\beta\big).$$

The above theorem shown in [1] is wrong. Do not believe in the second-hand knowledge.

For ease to understand, $\tilde R_\epsilon \geq \log_2 \big(1/\beta\big).$

$$\color{blue}\text{What does the above theorem mean?}$$

Why we call it corruption method?

Intuitively speaking, you can see that in every rectangle there are some noises such that they are almost monochromatic not pure monochromatic (When we try to find a rectangle with monochromatic 1, there are always 0 entries.). Finally, we find that the proportion of these corrupted areas are important, which indicate the communication complexity of solving a given function $f$.

Formally, we have the following statement. Theorem 2 is by Yao, and it means that given the entry of zeros make up at least $\alpha$ fraction of any rectangle $R$ except some small rectangles with size of $\beta$. As a result, we have the communication cost at least $\tilde R_\epsilon \geq \log_2 \big(\mu(f^{-1}(1))/\beta\big)$ (approximately).

Now, let us apply the corruption bound method to prove Theorem 1.

Assume that Alice and Bob have inputs of size exactly $\sqrt{n}$. Let $\mu$ denote the uniform probability distribution over all such inputs. Then, we have

$\mu(\textsf{DISJ}^{-1}_n(1)) = \frac{n-\sqrt{n} \choose \sqrt{n}}{n \choose \sqrt{n}} = \Omega(1)$ (It says that the proportion of 1-mass is some constant).

Next, we first forget the proof and believe the following claim is true.

$\textbf{Claim 1}$ For $\textsf{DISJ}$, we have some constants $\alpha, \delta$ and $\beta = 2^{-\delta \sqrt{n}}$ such that

$$\mu(R\cap \textsf{DISJ}^{-1}_n(0)) > \alpha \mu(R)-\beta$$

Or,

$\textbf{Claim 1}$ For $\textsf{DISJ}$, we have some constants $\alpha, \delta$ and $\beta$, $\mu(R) \geq 2^{-\delta \sqrt{n}}$ such that $\mu(R\cap \textsf{DISJ}^{-1}_n(0)) > \alpha \mu(R)$

Or,

$\text{Claim 1}$. For $\textsf{DISJ}$, we have some constants $\alpha, \delta$. Let $R\subset X \times Y$ be a rectangle of size $\lvert R \rvert \geq 2^{-\delta \sqrt{n}} N^2$. Then, we have $\lvert R\cap DISJ^{-1}(0) \rvert \geq \alpha \lvert R \rvert$ where $N = {n \choose \sqrt{n}}$.

Plugging the above the condition into the corruption bound method, we prove Theorem 1.

---

Reference

[1]. Sherstov, A.A., 2014. Communication complexity theory: Thirty-five years of set disjointness. In Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I 39 (pp. 24-43). Springer Berlin Heidelberg.