Thumbnail
Access Restriction
Subscribed

Author Lovett, Shachar
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Log-rank conjecture
Abstract We prove that any total boolean function of rank $\textit{r}$ can be computed by a deterministic communication protocol of complexity $\textit{O}(&sqrt;$ ċ $log(\textit{r})).$ Equivalently, any graph whose adjacency matrix has rank $\textit{r}$ has chromatic number at most $2^{O(&sqrt;rċlog(r))}.$ This gives a nearly quadratic improvement in the dependence on the rank over previous results.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-02-12
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 1
Page Count 9
Starting Page 1
Ending Page 9


Open content in new tab

   Open content in new tab
Source: ACM Digital Library