Aaronson–Ambainis conjecture: bounded low-degree polynomials have a variable of influence poly(Var/d)

Known. The Dinur–Friedgut–Kindler–O'Donnell theorem (STOC 2006) gives a maximum influence that is polynomial in $\mathrm{Var}[f]$ but exponentially small in $d$. Montanaro (2012) proved the conjecture for block-multilinear forms whose coefficients all have equal magnitude, and Bansal, Sinha and de Wolf (2022) for completely bounded block-multilinear forms. A 2020 claimed proof by Keller and Klein contained an error and was withdrawn. Bhattacharya (arXiv:2402.13952, ITCS 2025) proved that the conjecture holds for a non-negligible fraction of random restrictions when the variance is not too small, using the junta-approximation theorem of Filmus, Hatami, Keller and Lifshitz. Girish, Mittal, Nehoran and Raz (arXiv:2609.35327, September 2026, preprint) show that the analogues of the conjecture for biased product distributions and for Hamming slices are each equivalent to the original.

Related but distinct. The October 2026 OpenAI release includes an unrefereed AI-generated claim that the worst-case relation $R(f)$ for total Boolean functions is tight; that concerns worst-case query complexity of total functions, not the average-case simulation the conjecture is about.

If true, quantum query speed-ups over classical algorithms for total Boolean functions on average inputs are at most polynomial, which clarifies where exponential quantum speed-ups can live (structured problems, not unstructured search over total functions). The conjecture also bears on bounded-depth quantum circuits and on pseudo-random function testing. There are no engineering applications.

A proof of $\max_i\mathrm{Inf}_i[f]\ge(\mathrm{Var}[f]/d)^{C}$ for a universal constant for all bounded degree- multilinear , or an explicit family of bounded polynomials with . Any improvement of the DFKO bound to would be partial progress.