BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/389
DTSTAMP:20230914T125922Z
SUMMARY:Deterministic Communication Protocol for Functions with Bounded Ran
 k
DESCRIPTION:Speaker: Girish Varma\n\nAbstract: \nIn this talk we will go th
 rough the results in the paper titled "Communication is bounded by root of
  rank" by Shachar Lovett. The main result is to give a deterministic comm
 unication protocol which transfers at most  $O(\\sqrt{r}\\log r)$ bits fo
 r computing any function $f:X\\times Y \\rightarrow \\{0\,1\\}$ whose matr
 ix 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(\\s
 qrt{r}\\log r}$. This is a major improvement in the log-rank conjecture pr
 oposed by Lovasz and Saks. The proof is based on analyzing the discrepanc
 y of Boolean functions.\n
URL:https://www.tcs.tifr.res.in/web/events/389
DTSTART;TZID=Asia/Kolkata:20130802T143000
DTEND;TZID=Asia/Kolkata:20130802T160000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR