Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-084 | 8th October 2013 20:39

Communication is bounded by root of rank

RSS-Feed




Revision #1
Authors: Shachar Lovett
Accepted on: 8th October 2013 20:39
Downloads: 2793
Keywords: 


Abstract:

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



Changes to previous version:

Simplified proof of technical lemma; Added discussion on a conjecture related to matrix rigidity


Paper:

TR13-084 | 8th June 2013 06:24

Communication is bounded by root of rank





TR13-084
Authors: Shachar Lovett
Publication: 8th June 2013 06:30
Downloads: 6575
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint