Seminar Announcement
Speaker: Sreejata Kishor Bhattacharya, TIFR, Mumbai
Date: Friday, 14 March 2025
Time: 2:00 PM
Venue: Seminar Hall
Aaronson-Ambainis Conjecture is True for Random Restrictions
Sreejata Kishor Bhattacharya
TIFR. Mumbai.
14-03-25

---

Abstract

In an attempt to show that the acceptance probability of a quantum query algorithm making q queries can be well-approximated almost everywhere by a classical decision tree of depth ≤ poly(q), Aaronson and Ambainis proposed the following conjecture: let f be a degree d polynomial that maps the points over the Boolean hypercube to the interval [0,1], and f has a noticeable variance. Then the conjecture asserts that there exists a coordinate of f which has significant influence depending on the variance and the degree.

We show that, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.