## 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}\,.$

### Reference:

• [1] A. Kotlov, Rank and Chromatic Number of a Graph, Journal of Graph Theory 26(1), pages 1–8, 1997.
• [2] S. Lovett, Communication is bounded by root of rank, arXiv preprint arXiv:1306.1877, 2013.
• [3] D. Gavinsky and S. Lovett, En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations, ECCC Report Nr. 80, 2013.

S. Jukna, March 2014