ECCC-Report TR13-084https://eccc.weizmann.ac.il/report/2013/084Comments and Revisions published for TR13-084en-usTue, 08 Oct 2013 20:39:33 +0300
Revision 1
| Communication is bounded by root of rank |
Shachar Lovett
https://eccc.weizmann.ac.il/report/2013/084#revision1We 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.
Tue, 08 Oct 2013 20:39:33 +0300https://eccc.weizmann.ac.il/report/2013/084#revision1
Paper TR13-084
| Communication is bounded by root of rank |
Shachar Lovett
https://eccc.weizmann.ac.il/report/2013/084We 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.
Sat, 08 Jun 2013 06:30:54 +0300https://eccc.weizmann.ac.il/report/2013/084