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.6If $|\R|$ is sufficiently large, then for any labeling of $\R$, we have $\kw{\R}\leq 2 (\log|\R|)^2$.

**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$.

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

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$

- [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