Deterministic Communication Protocol for Functions with Bounded Rank

Speaker:

Time:

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

Venue:

• A-212 (STCS Seminar Room)

Organisers:

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.