Reminder: This post contains 3207 words
· 10 min read
· by Xianbin
Today is Fool’s day! Let us talk about fooling sets.
We can use fooling sets to prove lower bounds.
Lemma 1
\(\textbf{Lemma 1}\). Let \(f: X \times Y \to \{0,1\}\). If \(f\) has a fooling set \(S\) of size \(\lambda\), then the deterministic communication complexity \(D(f) \geq log_2 \lambda\).
Now, let us see what is a fooling set.
\(\textbf{Definition}\). A set \(S \subset X \times Y\) is called a fooling set (for \(f\)) if there exists a value \(z \in \{0,1\}\) such that
- For every \((x,y)\in S\), \(f(x,y) \ z\).
- For two distinct pairs \((x_1,y_1)\) and \((x_2,y_2)\) in \(S\), either \(f(x_1,y_2)\not = z\) or \(f(x_2,y_1) \not = z\).
Example 1.
Alice and Bob each hold a subset \(x, y\subseteq \{1,\ldots,n\}\). Let \(f = DISJ\). Then, a fooling set of size \(2^n\) is
\[C = \{A, \bar A\} \mid A\subseteq \{1,\ldots, n\}.\]
Proof of Lemma 1
\(\textbf{Proof of Lemma 1}\).
Definition (Rectangle). A combinatorial rectangle in \(X\times Y\) is a subset \(R \subseteq X\times Y\) such that \(R = A \times B\) for some \(A\subseteq X\) and \(B \subseteq Y\).
Definition (Partition). Let \(R_v\) be the set of inputs \((x,y)\) that reach node \(v\), then \(\{R_\ell\}_{\ell \in L}\) is a partition of \(X\times Y\).
Also, we can see that \(R_\ell\) is a rectangle.
\(\textbf{Lemma 2}\). If any partition of \(X\times Y\) into \(f\)-monochromatic rectangles requires at least \(t\) rectangles, then \(D(f) \geq \log_2 t\).
\(\textbf{Proof}\). Notice that the number of leaves in a protocol \(\mathcal{P}\) is the number of \(f\)-monochromatic rectangles caused by the partition of \(X\times Y\) induced by \(\mathcal{P}\). Therefore, there are at least \(t\) leaves. In the branch tree, each time, we have 2 choices, so the depth is at least \(\log_2 t\).
Now, let us prove Lemma 1. By the definition of fooling sets, no monochromatic rectangle contains more than \(\textbf{One}\) element in \(S\), so there are at least \(\lambda\) rectangles to cover \(S\). By Lemma 2, it is proved.
Lemma 1 Plus
Now, we improve Lemma 1 as follows.
\(\textbf{Lemma 3}\). Let \(\mu\) be a probability distribution of \(X\times Y\). If any \(f\)-monochromatic rectangle \(R\) has measure \(\mu(R) \leq \delta\), then \(D(f) \geq \log_2 1/\delta\).
To prove the above lemma, it is enough to show that there are at least \(1/\delta\) rectangles in any \(f\)-monochromatic partition of \(X\times Y\) and it is true since \(\mu(X\times Y) = 1\) and \(\mu(R) \leq \delta\).
\(\textbf{Lemma 4}\). Prove that the deterministic communication complexity of DISJ is \(D(DISJ) \geq \Omega(n)\).
\(\color{blue}\textbf{Proof 1}\). Let \(F = \{S, \bar S\}: S\in \{0,1\}^n\) be a fooling set. We can see that \(\lvert F\rvert = 2^n\). By Lemma 1, it is proved.
\(\color{blue}\textbf{Proof 2}\).
Consider two randomly-selected strings \(\color{blue}x\) and \(\color{blue}y\) each with \(n\)-bit. For each bit of \(x\), there is a probability \(3/4\) that the two strings do not have a value of one in this bit.
Let \(\mu\) be a uniform distribution over \(DISJ^{-1}_n(1)\), with support of \(3^n\) points (\(4^n (3/4)^n = 3^n\)). Let \(R = \mathcal{X}\times \mathcal{Y}\) be a 1-monochromatic rectangle of \(DISJ_n\) where \(\mathcal{X,Y}\subset \{1,\ldots,n\}\). Let \(X, Y\) denote the union of all sets in \(\mathcal{X, Y}\). We know that \(X\) and \(Y\) are disjoint, so we can construct a rectangle \(R'\) to be 1-monochromatic rectangle. So, \(\lvert R'\rvert \leq 2^{\lvert X\rvert+\lvert Y\rvert} \leq 2^n\). Then, \(\mu(R') = \frac{\lvert R' \rvert}{3^n}\leq (\frac{2}{3})^n\). By Lemma 3, it is proved.
Reference
[1]. Kushilevitz, E. and Nisan, N. (1996). Communication Complexity. Cambridge.
[2] Lecture 2. Lower Bounds for Deterministic Communication. Alexander Sherstov. CS 289A Communication Complexity.