The (log) rank lower bound for (deterministic) communication complexity was introduced by Mehlhorn and Schmidt [STOC'82]. It is known that this method does not always yield tight results (cf., e.g., Nisan and Wigderson [FOCS'94]), but the question of "how much off it is" has become a famous open problem. Lovasz and Saks [FOCS'88] conjectured that the (deterministic) communication complexity, DCC, is never larger than a polynomial in the log rank (lower bound), but only a constant improvement over the obvious bound of "DCC leq rank" was known so far. The current work shows "DCC leq tildeO(sqrt(rank))", which means "DCC is smaller than $2^{(0.5+o(1))(log rank)}$".
We prove that any total boolean function of rank r can be computed by a deterministic communication protocol of complexity $O(sqrt(r)log(r))$. Equivalently, any graph whose adjacency matrix has rank r has chromatic number at most $exp(sqrt(r)log(r))$. This gives a nearly quadratic improvement in the dependence on the rank over previous results.
See ECCC TR13-084.