\(
\def\<#1>{\left<#1\right>}
\newcommand{\c}{\mathsf{c}}
\newcommand{\rk}[1]{\mathrm{rk}(#1)}
\)
On the Log-Rank conjecture
Let $A$ be a boolean matrix, $\c(A)$ the deterministic
communication complexity of $A$, and $\rk{A}$ a real rank of $A$.
The upper bound $\c(A)\leq \rk{A}$ is trivial, because $A$ can have at most $2^{\rk{A}}$ distinct rows.
On the other hand, since $A$ can be covered by at most $2^{\c(A)}$ monochromatic rectangles,
the sub-additivity of rank implies that $\c(A)\geq \log_2\rk{A}$.
The Log-Rank Conjecture (Conjecture 4.19 in the book) states that
$\c(A)\leq (\log \rk{A})^{O(1)}$, i.e. that communication complexity is poly-logarithmic in the rank.
The goal of this comment is to tell about a recent progress concerning this conjecture.
Kotlov [1] improved the trivial upper bound $\c(A)\leq \rk{A}$ to $\c(A)\leq \log_2(4/3)\cdot\rk{A}$.
A much better upper bound was recently proved by Lowett [2].
Theorem (Lowett [2]):
There is a constant $c$ such that
\[
\c(A)\leq c\sqrt{\rk{A}}\cdot \log\rk{A}\,.
\]
Equivalently, every graph whose adjacency matrix has rank $r$ has chromatic number at most
$r^{O(\sqrt{r})}$.
A relation between rank, randomized and deterministic communication complexity was given in [3].
Theorem (Gavinsky and Lovett [3]):
There is a constant $c$ such that, if $R$ is the randomized communication
complexity of $A$, then
\[
\c(A)\leq c R\cdot \log^2\rk{A}\,.
\]