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