BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/966
DTSTAMP:20230914T125945Z
SUMMARY:On Protocols and Partitions
DESCRIPTION:Speaker: Suhail Sherif\n\nAbstract: \nAbstract: The first obse
rvation that one makes when analyzing communication protocols between Alic
e and Bob is that a cost c protocol partitions the input space into 2^c co
mbinatorial rectangles. An immediate consequence of this is that if a func
tion cannot be partitioned into 2^c combinatorial rectangles\, then it can
not be computed with c bits of communication.\nBut if a function CAN be pa
rtitioned into 2^c combinatorial rectangles\, can it be computed with c bi
ts of communication? In this talk\, we will look at known results on this
question:\n- If the 0s/1s of a function can be partitioned into 2^c combin
atorial rectangles\, it can be computed with c^2 bits of computation. [Aho
Ullman Yannakakis\, 1981]\n- There is a function with a partition into 2^
c combinatorial rectangles that requires (almost) c^2 bits of communicatio
n. [Göös Pitassi Watson\, 2015]\nThe latter result goes through the anal
ogous questions and answers in the simpler world of query complexity\, in
which "combinatorial rectangles" is replaced with "width-c subcubes".\nThi
s talk does not assume any prior knowledge of communication complexity.\n
URL:https://www.tcs.tifr.res.in/web/events/966
DTSTART;TZID=Asia/Kolkata:20190524T171500
DTEND;TZID=Asia/Kolkata:20190524T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR