We prove that any total boolean function of rank r can be computed by a deterministic communication protocol of complexity O(rlog(r)) . Equivalently, any graph whose adjacency matrix has rank r has chromatic number at most 2O(rlog(r)) . This gives a nearly quadratic improvement in the dependence on the rank over previous results.
展开▼
