We prove that any total boolean function of rank $r$ can be computed by adeterministic communication protocol of complexity $O(sqrt{r} cdot log(r))$.Equivalently, any graph whose adjacency matrix has rank $r$ has chromaticnumber at most $2^{O(sqrt{r} cdot log(r))}$. This gives a nearly quadraticimprovement in the dependence on the rank over previous results.
展开▼