C1: Distributional Disjointness (Non information theory)

March 29, 2024

• Theorem 1
• Proof of Lemma 1.
• Appendix
  • Proof of Claim 1.
• Reference

This post is based on [1]. For a distribution $\mu$, we use $D^\mu_\epsilon(F)$ to denote the $\epsilon$-error distributional communication complexity that is the minimum cost of deterministic protocol $\Pi$ such that $P_\mu[\Pi(X,Y)=F(X,Y)] \geq 1-\epsilon.$ On the other hand, the cost if for the best deterministic protocol that gives the correct answer for $F$ on at least $(1-\epsilon)$ fraction of all inputs of $X \times Y$ given $\mu$.

We say that $DISJ(X, Y) = 1$ if and only if $X \cap Y = \emptyset$. We will prove the following theorem.

Theorem 1

$\textbf{Theorem 1}$. There exists a distribution $\mu$, such that $D^\mu_\epsilon(DISJ_n)\geq \Omega(n)$ where $\epsilon < 0.01$.

$\color{red}\textbf{Notice}$ that $\mu$ is not a product distribution (i.e., $\mu_X(x)\mu_Y(y) = \mu(x,y) )$ because the common choice of i. Therefore, it does not violate the $\tilde O(\sqrt{n})$ algorithm for DISJ.

$\textbf{Proof}$. We first give the distribution $\mu$. Let $\color{blue} n = 4t- 1$ and let $\pi = (S_X, S_Y, \{i\})$ be an arbitrary partition of $[n]$ such that $\lvert S_X\rvert = \lvert S_Y\rvert = 2t-1$ ($i\in[n]$). Now, let us construct the input for the first player, Alice. We select $t$ elements from $S_X \cup \{i\}$ uniformly at random as $X$. For the player Bob, we select $t$ elements from $S_Y\cup \{i\}$ uniformly at random as $Y$. We know that with probability $1/2$, we can select the $i$ in the input. For simplicity, we use $X_0$ to denote the input $X$ such that $i \not \in X$. We use $X_1$ to denote the input $X$ such that $i\in X$. Similarly, we define $Y_0$ and $Y_1$.

In the above distribution $\mu$, we have four types of input, i.e., $(X_1,Y_1)$ (we use $I$ to denote the set of such an input) and other three cases $(X_0,Y_0), (X_0, Y_1), (X_1, Y_0)$ (we use $J$ to denote such inputs) . It is easy to find that $\mu(J) = 3/4$.

The following lemma is the key to proving this theorem.

$\textbf{Lemma 1.}$ Given any rectangle $R$, we have $\color{blue} \mu(R\cap J) \geq \alpha \mu(R\cap I) - 2^{-\delta n}$ where $\alpha,\delta$ are some constants.

Suppose $D^\mu_\epsilon = k$. Then, protocols will partition $\{0,1\}^n \times \{0,1\}^n$ into at most $2^k$ rectangles. Let $\color{blue} R_1,R_2,\ldots,R_\ell$ denote the monochromatic $\color{blue} \text{rectangles with value} 1$ where $\ell = 2^k$. Because we allow $\epsilon$ error for protocols, $\mu(\cup_{i=1}^\ell R_i \cap I) \geq \frac{3}{4} - \epsilon$ and $\mu(\cup_{i=1}^\ell R_i \cap J) \leq \epsilon$ (Recall that $\mu(I) = 3/4$ and $\mu(J)=1/4$. Notice that here $J$ is the set of announcing 0, so the probability of announcing 1 is 0).

Thus, we have

$$\epsilon \geq \mu(\bigcup_{i=1}^\ell (R_i\cap J)) \geq \sum_{i=1}^\ell (\alpha \mu(R_i \cap I) - 2^{-\delta n}$$ $$\geq \alpha(\frac{3}{4}-\epsilon) - 2^{k-\delta n}$$

So, $k\geq \Omega(n)$.

Proof of Lemma 1.

$\color{blue}{\text{Step 1> Generate random input } (x_0,y_0), (x_1,y_1)}$

Let $\pi:=(S_X,S_Y,\{i\})$ be the random partition of $[n]$ mentioned above. Recall the process of $\pi$, $X$ and $Y$ are independent.

Given $\pi$, we define the following. Let $R = \mathbb{X}\times \mathbb{Y}$ be a rectangle where $\mathbb{X,Y}\subseteq 2^{[n]}$.

$$\begin{aligned} p_{X}(\pi):=\mathcal{P}[X\in \mathbb{X} \mid \pi] \\ p_{X_0}(\pi):= \mathcal{P}[X_0\in \mathbb{X} \mid \pi] = \mathcal{P}[X\in \mathbb{X} \mid \pi, i\not \in X] \\ p_{X_1}(\pi):=\mathcal{P}[X_1\in \mathbb{X} \mid \pi] = \mathcal{P}[X\in \mathbb{X} \mid \pi, i\in X]\\ p_{Y}(\pi):=\mathcal{P}[Y\in \mathbb{X} \mid \pi] \\ p_{Y_0}(\pi):= \mathcal{P}[Y_0\in \mathbb{X} \mid \pi] = \mathcal{P}[Y\in \mathbb{X} \mid \pi, i\not \in Y]\\ p_{Y_1}(\pi):=\mathcal{P}[Y_1\in \mathbb{X} \mid \pi] \mathcal{P}[Y\in \mathbb{X} \mid \pi, i\in Y]\\ \end{aligned}$$

Then, by the property of rectangle and $X \perp Y$, we have

$$\begin{aligned} \mathcal{P}[(X_0,Y_0)\in \mathbb{X}\times \mathbb{Y}] = E[p_{X_0}(t)p_{Y_0}(t)]\\ \mathcal{P}[(X_1,Y_1)\in \mathbb{X}\times \mathbb{Y}] = E[p_{X_1}(t)p_{Y_1}(t)] \end{aligned}$$

Now, let us rewrite elements of the goal of our proof.

$$\begin{aligned} \mu(I\cap R) = \frac{1}{4}\mathbb{E}_\pi[p_{X_1}(\pi)p_{Y_1}(\pi)]\\ \mu(J\cap R) = \frac{3}{4}\mathbb{E}_\pi[p_{X_0}(\pi)p_{Y_0}(\pi)] \end{aligned}$$

To prove Lemma 1, we need to connect $p_{X_0}(\pi)p_{X_1}(\pi)$ and $p_{Y_0}(\pi)p_{Y_1}(\pi)$ together. Intuitively speaking, they should be close. It is not hard to find the connection.

$\color{blue}{\text{Step 2> Define Bad Events}}$

To build the connection, we define bad events as follows.

$\textbf{Bad Event}$. We say a partition $\pi=(S_X, S_Y,\{i\})$ is $X$-bad if

$$\color{blue} \begin{aligned} p_{X_1}(\pi) < \frac{1}{3}p_{X_0}(\pi) - 2^{-\epsilon n} \text{ (1)} \end{aligned}$$

$\textbf{Claim 1}$. Let $Bad(\pi)$ be the indicator of the event $\pi=(S_X,S_Y,\{i\})$ being Bad. We have $\color{blue} \mathbb{E}_\pi[p_{X_0}(\pi)p_{Y_0}(\pi)Bad(\pi)] \leq \frac{4}{5} \mathbb{E}_\pi[p_{X_0}(\pi)p_{Y_0}(\pi)] \text{ (2)}$

Now, we have (using Inequality (1) and (2)).

$$\begin{aligned} \mathcal{P}[(X_1,Y_1)\in R] = \mathbb{E}_{\pi}[p_{X_1}(\pi) p_{Y_1}(\pi)] \\ \geq \mathbb{E}_{\pi}[p_{X_1}(\pi) p_{Y_1}(\pi)(1-Bad(\pi)]\\ \geq \mathbb{E}_{\pi}[(\frac{p_{X_0}(\pi)}{3}-2^{-\epsilon n}) (\frac{p_{Y_0}(\pi)}{3}-2^{-\epsilon n})(1-Bad(\pi)]\\ \geq \alpha' \mathbb{E}_\pi[p_{X_0}(\pi)p_{Y_0}(\pi)]-2^{-\Omega(n)} \\ = \alpha'\mathcal{P}[(X_0,Y_0)\in R] - 2^{-\Omega(n)} \end{aligned}$$

Therefore,

$$4\mu(J\cap R) \geq \frac{4\alpha'}{3}\mu(I\cap R)-2^{-\Omega(n)}\\$$

Thus,

$$\mu(J\cap R) \geq \frac{\alpha'}{3}\mu(I\cap R)-2^{-\Omega(n)}\\ =\alpha\mu(I\cap R)-2^{-\Omega(n)}$$

---

Appendix

Proof of Claim 1.

Some fact: $p_{X_0}(\pi) + p_{X_1}(\pi) = 2p(\pi)$. To prove Claim 1, we need to prove the following Claim 1.1.

$\textbf{Claim 1.1}$. For any set $S_Y \subseteq [n] \text{ such that} \mid S_Y \mid = 2t - 1$, $\mathcal{P}(\pi \text{ is } X \text{-bad} \mid S_Y) < 1/5$

$\textbf{Proof}$. By the definition of (1), we know that $p_{1}(\pi) \geq 2^{-\epsilon n}$ (otherwise, bad events will not happen and it is proved).

Recall that $X = \{\mathcal{X}: \mathcal{X}\subseteq [n], \lvert \mathcal{X}\rvert=t, \mathcal{X}\subseteq S_\mathcal{X} \cup {\color{red} \{i\}}\}$.

We define $X' = \{\mathcal{X}: \mathcal{X}\subseteq [n], \lvert \mathcal{X}\rvert=t, \mathcal{X}\subseteq S_\mathcal{X} \cup {\color{red}\emptyset} \}$.

Let us select $s$ uniformly at random in $X$, then we have

$$\mathcal{P}[i\not \in X] = \frac{\lvert X'\lvert }{\lvert X\rvert}$$

Thus,

$$p_{X_0}(\pi) =\mathcal{P}[ X\in \mathbb{X} \mid S_Y, i\not \in X]\\ =\frac{\lvert X' \rvert}{2t-1 \choose t} = \frac{\lvert X' \rvert}{\lvert X \rvert} p(\pi)\cdot 2\\ =2p(\pi)\mathcal{P} [i\not \in s]$$

where $s = X \in \mathbb{X}$ under $\pi$.

Similarly, we get that

$$p_{X_1}(\pi) = 2p(\pi)\mathcal{P} [i \in s]$$

Combining with the definition of $X$-bad, we get that

$$\mathcal{P}[i\in s] < \frac{1}{3}\mathcal{P}[i\not \in s] - \frac{2^{-\epsilon n}}{2p(\pi)}$$

So, $\color{blue} \mathcal{P}(i\in s) < 1/4. \text{ (3) }$

Now let $\{i_1,\ldots,i_{2t}\}$ denote $[n]\setminus S_Y$ and let $\textbf{s}=\{s_1,\ldots,s_{2t}\}$. We say that $s_j = 1$ if $i_j \in s$.

• i). It is easy to see that $\mathcal{P}(s_j) \leq 1/2$ ($s$ has size $t$).
• ii). $\mathcal{P}(s_j) < 1/4$ from (3).

We prove this cliam by contradiction. Suppose that the bad event happens with probability at least 1/5. So, 1/5 of $\{s_1,\ldots,s_{2t}\}$ is $X$-bad, which corresponds to ii). For the remaining, it corresponds to i).

Consider $\textbf{s}$, we compute its entropy as follows.

$$\textbf{H(s)}=\textbf{H}(s_1,\ldots,s_{2t})\leq \sum_{i=1}^{2t} \textbf{H}(s_i) \\\leq \frac{2t}{5}\textbf{H}(1/4) + \frac{8t}{5}\textbf{H}(1/2) < 1.93 t$$

On the other hand,

$$\textbf{H(s)} = \log \lvert X\rvert \geq \log\big( p(\pi) {2t \choose t}\big) \leq \log \big( 2^{-\delta n} {2t \choose t}\big)\\ \geq \log \big( \frac{2^{2t}}{c\sqrt{t}} 2^{-\delta n}\big) = t(2-4\delta - o(1))$$

By selecting $\delta$ to be very small, there is a contradiction. So, Claim 1.1 is proved.

Finally, we can prove Claim 1.

Since $Bad(\pi) \leq Bad_X(\pi) + Bad_Y(\pi)$, we only need to prove $\mathbb{E}_\pi[p_{X_0}(\pi)p_{Y_0}(\pi)Bad_X(\pi)] \leq \frac{2}{5}\mathbb{E}_T[p_{X_0}(\pi)p_{Y_0}]$ by symmetry.

When fixing $S_Y$, we fix $S_X\cup \{i\}$. Therefore, we fix $p(\pi)$ (because $\color{blue} S_X\cup \{i\}$ is fixed ) and $p_{Y_0}(\pi)$ (because $\color{blue} S_Y \cup {\{\text{no } i = \emptyset}\} = S_Y$).

It is sufficient to prove Claim 1 by looking the probability for each $S_Y$,

$$\mathbb{E}_\pi[p_{X_0}(\pi)p_{Y_0}(\pi)Bad_X(\pi) \mid S_Y]\\ =c\cdot \mathbb{E}_\pi[p_{X_0}(\pi)Bad_X(\pi) \mid S_Y]\\ \leq 2c\mathbb{E}_\pi[p(\pi)Bad_X(\pi) \mid S_Y]\\ =2cr\mathbb{E}[Bad_X(\pi)\mid S_Y]\\ =2cr\mathcal{P}[Bad_X(\pi)=1\mid S_Y]\\ \leq \frac{2cr}{5}\\ =\frac{2}{5}c \mathbb{E}_\pi[p(\pi) \mid S_Y]\\ \frac{2}{5}c \mathbb{E}_\pi[p_{X_0}(\pi) \mid S_Y]\\ =\frac{2}{5}\mathbb{E}[p_{X_0}(\pi)p_{Y_0}(\pi) \mid S_Y]$$

So, we prove Claim 1.1.

Reference

[1]. Razborov, Alexander A. “On the distributional complexity of disjointness.” International Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990.

[2]. Kushilevitz, E. and Nisan, N. (1996). Communication Complexity. Cambridge.