## Communication is bounded by root of rank

by Shachar Lovett.

#### Oded's comments

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)}$".

#### The original abstract

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.

Back to
list of Oded's choices.