Communication is Bounded by Root of Rank
Shachar Lovett · Journal of the ACM · 2016
We prove that any total boolean function of rank r can be computed by a deterministic communication protocol of complexity O (√ ċ log( r )). Equivalently, any graph whose adjacency matrix has rank r has chromatic number at most 2 O (√ r ċlog( r )) . This gives a nearly quadratic improvement in the dependence on the rank over previous results.