T1: Fooling Sets

April 01, 2024

• Lemma 1
  • Example 1.
• Proof of Lemma 1
• Lemma 1 Plus
• Reference

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.