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)
