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