Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR13-084 | 8th October 2013 20:39

#### Communication is bounded by root of rank

Revision #1
Authors: Shachar Lovett
Accepted on: 8th October 2013 20:39
Keywords:

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

### Paper:

TR13-084 | 8th June 2013 06:24

#### Communication is bounded by root of rank

TR13-084
Authors: Shachar Lovett
Publication: 8th June 2013 06:30
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.