BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/783
DTSTAMP:20230914T125938Z
SUMMARY:A Composition Theorem for Randomized Query Complexity
DESCRIPTION:Speaker: Suhail Sherif\n\nAbstract: \nAround a week ago\, a gro
up of researchers* proved that the randomized query complexity of f compos
ed with g is lower bounded by the product of the randomized query complexi
ties of f and g\, albeit with suboptimal parameters. This proof of theirs
is quite simple and so I wish to give a decently good exposition of it.\nI
n this talk\, I plan to:\n\n- introduce query complexity\n- show Yao's lem
ma and how it simplifies dealing with randomized algorithms\n- present the
proof from the paper\n* Anurag Anshu\, Dmitry Gavinsky\, Rahul Jain\, Sri
jita Kundu\, Troy Lee\, Priyanka Mukhopadhyay\, Miklos Santha and Swagato
Sanyal\, in their paper "A Composition Theorem for Randomized Query Comple
xity" (arXiv:1706.00335)\n
URL:https://www.tcs.tifr.res.in/web/events/783
DTSTART;TZID=Asia/Kolkata:20170609T171500
DTEND;TZID=Asia/Kolkata:20170609T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR