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

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

\[\mu(R \cap f^{-1}(0)) \geq \alpha \mu(R) - \beta\]\(\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

Then, for all \(\epsilon > 0\),

\[R_\epsilon \geq \log_2 \big((\alpha \mu(f^{-1}(1)) -\epsilon)/\beta\big).\]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(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.