Tata Institute of Fundamental Research
Aaronson-Ambainis Conjecture Is True For Random Restrictions
STCS Student Seminar
Speaker:
Sreejata Kishor Bhattacharya (TIFR)
Organiser:
Varun Ramanathan
Date:
Friday, 27 Dec 2024, 10:30 to 11:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The Aaronson-Ambainis conjecture is a very well known conjecture which states the following: let P be a degree d n-variate real polynomial P such that 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 has important implications to quantum query complexity.
In this work, we show that Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given function. (Based on work that will appear in ITCS 2025)
| Speaker: | Sreejata Kishor Bhattacharya (TIFR) |
| Organiser: | Varun Ramanathan |
| Date: | Friday, 27 Dec 2024, 10:30 to 11:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The Aaronson-Ambainis conjecture is a very well known conjecture which states the following: let P be a degree d n-variate real polynomial P such that 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 has important implications to quantum query complexity.
In this work, we show that Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given function. (Based on work that will appear in ITCS 2025)