__
Revision #1 to TR13-084 | 8th October 2013 20:39
__
#### Communication is bounded by root of rank

**Abstract:**
We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on the rank over previous results.

**Changes to previous version:**
Simplified proof of technical lemma; Added discussion on a conjecture related to matrix rigidity

__
TR13-084 | 8th June 2013 06:24
__

#### Communication is bounded by root of rank

**Abstract:**
We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on the rank over previous results.