BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/943
DTSTAMP:20230914T125944Z
SUMMARY:The Polynomial Method Strikes Back: Tight Quantum Query Bounds via
Dual Polynomials
DESCRIPTION:Speaker: Robin Kothari (Microsoft Research\nRedmond\, USA)\n\nA
bstract: \nAbstract: The approximate degree of a Boolean function f is th
e least degree of a real polynomial that approximates f pointwise to erro
r at most 1/3. Approximate degree is known to be a lower bound on quantum
query complexity. We use approximate degree to prove optimal or nearly
optimal lower bounds on the quantum query complexity of several problems\
, resolving open questions from prior work. The problems studied include
k-distinctness\, image size testing\, k-junta testing\, approximating sta
tistical distance\, approximating Shannon entropy\, and surjectivity. Thi
s work was presented at QIP 2018 and STOC 2018\, and is available at http
s://arxiv.org/abs/1710.09079. This is joint work with Mark Bun and Justin
Thaler.\n
URL:https://www.tcs.tifr.res.in/web/events/943
DTSTART;TZID=Asia/Kolkata:20190226T160000
DTEND;TZID=Asia/Kolkata:20190226T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR