School of Technology and Computer Science Seminars
Deterministic Communication Protocol for Functions with Bounded Rank
by Mr. Girish Varma (School of Technology and Computer Science, TIFR)
Friday, August 2, 2013
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminar Room) )
at Colaba Campus ( A-212 (STCS Seminar Room) )
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. |