| Description |
In this talk we will go through the results in the paper titled "Communication is bounded by root of rank" by Shachar Lovett.
The main result is to give a deterministic communication protocol which transfers at most $O(\sqrt{r}\log r)$ bits for computing any function $f:X\times Y \rightarrow \{0,1\}$ whose matrix has rank $r$. Equivalently this can be stated as saying that any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r}\log r}$. This is a major improvement in the log-rank conjecture proposed by Lovasz and Saks. The proof is based on analyzing the discrepancy of Boolean functions.
|