Processing math: 0%

$\def\<#1>{\left<#1\right>} \newcommand{\R}{\mathcal{R}} \renewcommand{\deg}[2]{\mathrm{deg}_{#2}(#1)} \newcommand{\kw}[1]{\mathfrak{c}(#1)}$

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