Deterministic Communication Protocol for Functions with Bounded Rank



Friday, 2 August 2013, 14:30 to 16:00


  • A-212 (STCS Seminar Room)


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.