\( \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}\,. \]


S. Jukna, March 2014