BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1507
DTSTAMP:20241227T050311Z
SUMMARY:Aaronson-Ambainis Conjecture Is True For Random Restrictions
DESCRIPTION:Speaker: Sreejata Kishor  Bhattacharya (TIFR)\n\nAbstract: \nTh
 e Aaronson-Ambainis conjecture is a very well known conjecture which state
 s the following: let P be a  degree d n-variate real polynomial P such th
 at for any x in the Boolean hypercube\, P(x) lies between 0 and 1. Then\, 
 P has a coordinate with influence >= poly(var[f]\,1/d). This conjecture ha
 s important implications to quantum query complexity.In this work\, we sho
 w that Aaronson-Ambainis conjecture is true for a non-negligible fraction 
 of random restrictions of the given function. (Based on work that will app
 ear in ITCS 2025)\n
URL:https://www.tcs.tifr.res.in/web/events/1507
DTSTART;TZID=Asia/Kolkata:20241227T103000
DTEND;TZID=Asia/Kolkata:20241227T113000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR