BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/913
DTSTAMP:20230914T125943Z
SUMMARY:Communication and Rank
DESCRIPTION:Speaker: Suhail Sherif\n\nAbstract: \nAbstract: The communicati
on complexity of a function f(x\,y) is the number of bits that Alice and B
ob need to communicate in order to compute f\, when Alice has x and Bob ha
s y. It is a long-held belief that this quantity\, which we gave an operat
ional definition of\, should be closely related to the rank of the communi
cation matrix of f.\nIn our recent work\, "The Log-Approximate-Rank Conjec
ture is False"\, we show that randomized communication and approximate ra
nk do not have the close relationship that we would have liked to believe
\, thus refuting the titular conjecture.\nIn this talk\, we will discuss
why communication and rank are believed to be related. We will also see th
at our counter-example actually stems from a poor understanding of the mo
del of parity decision trees\, leaving us with fundamental open problems
even in such simple models of computation (joint work with Arkadev Chatto
padhyay and Nikhil Mande).\n
URL:https://www.tcs.tifr.res.in/web/events/913
DTSTART;TZID=Asia/Kolkata:20181102T171500
DTEND;TZID=Asia/Kolkata:20181102T184500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR