4 Upper bound on the deterministic communication complexity of $\operatorname{eval}$

Definition 4.1 The non-monochromatic protocol

Given a coloring $c : \{ x \mid \operatorname{eval}x = 1\} \to [C]$, writing $a_i$ the vector whose $j$-th coordinate is $x_j$ except when $j = i$ in which case it is $-\sum _{j \ne i} x_j$, we define the non-monochromatic protocol for $c$ by making participant $i$ do “Send the $t / d$-th bit of $c(a_i)$ until time $\lceil \log _2\chi _d(G)\rceil $, then send $1$ iff $c(a_i)$ agrees with the broadcast from time $1$ to time $\lceil \log _2\chi _d(G)\rceil $ read as a color” and “Send $1$ iff the broadcasts from time $\lceil \log _2\chi _d(G)\rceil $ to time $\lceil \log _2\chi _d(G)\rceil + d$ were all $1$”.

Lemma 4.2 The non-monochromatic protocol is valid

If $c$ is a coloring such that all monochromatic forbidden patterns are trivial, then the non-monochromatic protocol for $c$ is valid in time $\lceil \log _2\chi _d(G)\rceil + d$.

Proof ▶

We have

\[ \text{answer is } 1 \iff \text{ all $a_i$ have the same color } \iff \text{ all $a_i$ are equal } \iff \sum _i x_i = 0 \]

where the first equivalence holds by definition, the second one holds by assumption and the third one holds since the $a_i$ form a forbidden pattern.

Theorem 4.3 Upper bound for $D(\operatorname{eval})$ in terms of $\chi _d(G)$

\[ D(\operatorname{eval}) \le \lceil \log _2\chi _d(G)\rceil + d \]

Proof ▶

Using Lemma 3.2, find some coloring $c$ of $\{ x \mid \sum _i x_i = 0\} $ in $\chi _d(G)$ colors such that all monochromatic forbidden patterns are trivial. Then Lemma 4.2 tells us that the non-monochromatic protocol for $c$ is valid in time $\lceil \log _2\chi _d(G)\rceil + d$.

Corollary 4.4 Upper bound for $D(\operatorname{eval})$ in terms of $r_d(G)$

\[ D(\operatorname{eval}) \le 2d\log _2\frac N{r_d(G)} \]

Proof ▶

Putting Theorem 4.3 and Lemma 1.7 together, we get

\[ D(\operatorname{eval}) \le \left\lceil \log _2\frac{2dN^d\log N}{r_d(G)}\right\rceil \le 2d\log _2\frac N{r_d(G)} \]

Chandra-Furst-Lipton

4 Upper bound on the deterministic communication complexity of \(\operatorname{eval}\)