BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/700
DTSTAMP:20230914T125935Z
SUMMARY:Randomized Sabotage Complexity
DESCRIPTION:Speaker: Suhail Sherif\n\nAbstract: \nOne of the famous open pr
 oblems in randomized query complexity is the composition question: Is R(f 
 o g) = Omega(R(f)R(g)) for all boolean functions f and g. Shalev Ben-David
  and Robin Kothari recently showed that this is true for a restricted case
 \, where R(f o h o g) = Omega(R(f)R(h)R(g)) for some fixed h. To do so\, t
 hey introduced randomized sabotage complexity. This complexity measure has
  several nice properties.\nIn this talk\, I will present the randomized sa
 botage complexity measure\, go through some of its properties and present 
 the proof of the restricted composition theorem. Most of this will just be
  through making simple observations\, almost no background is required.\n
URL:https://www.tcs.tifr.res.in/web/events/700
DTSTART;TZID=Asia/Kolkata:20160729T160000
DTEND;TZID=Asia/Kolkata:20160729T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR