Lemma 3.6: making coverings disjoint

The proof of this lemma in the book is not quite rigorous: so as it is, the argument does not ensure that the number of all rectangles decreases by at least the factor of $1/2$ in each round: only the number "differently than $R$ labeled rectangles" decreases by this factor, where the communicated rectangle $R$ may be different in different rounds. One has to trick to get things work right ...

I am thankful to Hans Ulrich Simon for pointing to this issue.

Below we give a corrected proof of Lemma 3.6 which follows more tightly the original argument of Aho, Ullman and Yannakakis [1] (for two labels).

Suppose, we have a finite collection $\R=\{X_u\times Y_u\colon u\in V\}$ of (not-necessarily disjoint) rectangles covering the entire rectangle $X\times Y$. Suppose also that each rectangle $R\in\R$ has its label. The only requirement is that the labeling must be legal in that overlapping rectangles have the same label.

In the find-a-rectangle game on $\R$, Alice gets an $x\in X$, Bob gets an $y\in Y$, and their goal is to find a label of a rectangle containing $(x,y)$. Note that the answer (label) is unique for each point $(x,y)$: if the point belongs to more than one rectangle, then (due to the legality of the labeling) all these rectangles must have the same label. Let $\kw{\R}$ denote the deterministic communication complexity of such a game for $\R$. The following lemma was proved by Aho, Ullman, Yannakakis [1] when only two labels ($0$ and $1$) of rectangles are allowed. The argument, however, almost readily extends to any number of labels.

Lemma 3.6 If $|\R|$ is sufficiently large, then for any labeling of $\R$, we have $\kw{\R}\leq 2 (\log|\R|)^2$.

Proof: We have a collection $\R=\{X_u\times Y_u\colon u\in V\} $ of (not-necessarily disjoint) rectangles covering the entire rectangle $X\times Y$. This collection is known to both players, Alice and Bob. Consider two graphs $G_0$ and $G_1$ on the same set of vertices $V=\R$; hence, vertices are rectangles. Two rectangles $u=X_u\times Y_u$ and $w=X_w\times Y_w$ are adjacent in $G_0$ if $X_u\cap X_w\neq\emptyset$, and are adjacent in $G_1$ if $Y_y\cap Y_w\neq \emptyset$. For a rectangle $u\in V$, let $\deg{u}{0}$ (resp., $\deg{u}{1}$) denote the degree of a node $u$ in $G_0$ (resp., in $G_1$). The graphs $G_0$ and $G_1$ are also known to both players. Suppose now that some pair $(x,y)\in X\times Y$ arrives. The element $x$ is seen only to Alice, and $y$ only to Bob.

Protocol: The protocol works in rounds. After each round either the label of a rectangle containing the pair $(x,y)$ is found (and the protocol finishes), or the size of the new set $V$ of rectangles is at most $3/4$ of the old size. A round is carried as follows.

Alice looks for a rectangle $u=X_u\times Y_u$ in $V$ such that $x\in X_u$ and $\deg{u}{0}\leq 3|V|/4$. If Alice finds such a rectangle $u$, she sends it to Bob (using $\log|V|$ bits). Bob checks whether $y$ belongs to the right side $Y_u$ of this rectangle. If $y\in Y_u$, then the protocol finishes: both players know that $(x,y)\in X_u\times Y_u$. If $y\not\in Y_u$, then both players replace the set $V$ of rectangles by the set consisting all $\deg{u}{0}$ neighbors of $u$ in $G_0$. (Since $y\not\in Y_u$, the rectangle $u$ itself cannot contain the pair $(x,y)$.) Thus, the size of the new set $V$ of rectangles is at most $3/4$ of the old size. The graph $G_0$ is replaced by the induced subgraph of $G_0$ on the new set $V$.
If Alice does not find an appropriate rectangle $u$ in step (1), she tells this to Bob (using one bit). Bob then looks for a rectangle $w=X_w\times Y_w$ in $V$ with $y\in Y_w$ and $\deg{w}{1}\leq 3|V|/4$. If Bob finds such a $w$, he sends it to Alice (using $\log|V|$ bits). In the first case (when Bob finds a corresponding rectangle $w$) Alice acts symmetrically. That is, either $x\in X_w$ in which case the protocol finishes, or $x\not\in X_w$ in which case the round finishes with the set $V$ of rectangles updated. The graph $G_1$ is replaced by the induced subgraph of $G_1$ on the new set $V$.

We claim that if after any one round neither Alice nor Bob could find an appropriate rectangle in the current set $V$ of remaining rectangles, then the players have enough information to determine the label of a rectangle containing our pair $(x,y)$. Indeed, in this case, both players know that every rectangle $u\in V$ containing $x$ has $\deg{u}{0}>3|V|/4$ and every rectangle $w\in V$ containing $y$ has $\deg{w}{1}>3|V|/4$. Therefore, every rectangle containing the pair $(x,y)$ has degree $>3|V|/4$ in both graphs $G_0$, $G_1$ and thus has degree $>|V|/2$ in their intersection $G=G_0\cap G_1$. That is, every rectangle in $V$ containing the pair $(x,y)$ belongs to the set $V'\subseteq V$ of all rectangles in $V$ that have degree $>|V|/2$ in the graph $G$.

Claim: All rectangles in $V'$ have the same label.

Proof: Let $u,v\in V$ be rectangles of degree $>|V|/2$ in $G$. Then there is a rectangle $w\in V$ which is adjacent to both $u$ and $v$ in $G$. But two rectangles are adjacent in $G$ if and only if they have a nonempty intersection. Since the labeling of rectangles is legal, it follows that $u,v$ and $w$ have the same label. $\Box$

Since every rectangle containing $(x,y)$ belongs to $V'$, the players can output the label of any rectangle from $V'$: Claim ensures that this is a correct answer.

Number $K$ of communicated bits: We have $r\leq C\log|V|$ rounds where $C:=1/\log_2(4/3)=2.40942\ldots < 2.5$, and in each round at most $1+\log|V|$ bits are communicated. Hence, $K\leq C\log^2|V| +C\log|V|$. But actually, in each of the subsequent rounds, the set $V$ of "still alive" rectangles decreases by $3/4$. Namely, we have $r$ sets $V_1,\ldots,V_r$ of rectangles, where $V_1=V$ and $|V_{i+1}|\leq (3/4)|V_i|\leq (3/4)^i|V|$. This yields a better upper bound $K\leq 2\log^2|V|$. Indeed, \begin{align*} K&=\sum_{i=1}^r(1+\log|V_i|)\leq r+\sum_{i=1}^r\log[(3/4)^i|V| = r+r\log|V|-\sum_{i=1}^ri\log(4/3)\\ &=r+r\log|V|-\frac{r(r+1)}{2C}\leq r\log|V|-\left(\frac{r^2}{2C}-r\right) \leq r\log|V|-\left(\frac{r^2}{5}-r\right) \leq r\log|V|- \frac{r^2}{8}\,, \end{align*} where the last inequality holds for all $r\geq 30$. Now, if $r\leq 2\log|V|$, then $K\leq 2\log^2|V|$, and we are done. So, assume that $r>2\log|V|$. Then \begin{align*} \frac{K}{\log|V|}&\leq r-\frac{r^2}{8\log|V|} \leq 2.5\log|V|-\frac{4\log^2|V|}{8\log|V|} = \left(2.5-0.5\right)\log|V| = 2\log|V|\,. \end{align*} Thus, in both cases, the total number of communicated bits is $K\leq 2\log^2|V|=2\log^2|\R|$, as claimed. $\Box$

Reference:

[1] A. Aho, J. Ullman and M. Yannakakis (1983): On notions of information transfer in VLSI circuits, in: 15th STOC, 133-139. paper

S. Jukna, 27.04.2020