Tata Institute of Fundamental Research

Deterministic Communication Protocol for Functions with Bounded Rank

Student Seminar
Speaker: Girish Varma
Organiser: Shidhesh Supekar
Date: Friday, 2 Aug 2013, 14:30 to 16:00
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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.