Aaronson–Ambainis influential-variable conjecture
Let $n, d \ge 1$ and let $p : \{-1,1\}^n \to \mathbb{R}$ be a polynomial of degree at most $d$, $$p(x) = \sum_{S \subseteq [n],\ |S| \le d} \widehat{p}(S) \prod_{j \in S} x_j,$$ with $|p(x)| \le 1$ for every $x \in \{-1,1\}^n$. For $X$ uniform on $\{-1,1\}^n$ and $X^{(i)}$ equal to $X$ with its $i$th coordinate flipped, let $$\operatorname{Var}(p) = \mathbb{E}\bigl[(p(X) - \mathbb{E}\,p(X))^2\bigr], \qquad \operatorname{Inf}_i(p) = \mathbb{E}\left[ \left( \frac{p(X) - p(X^{(i)})}{2} \right)^2 \right] = \sum_{S \ni i} \widehat{p}(S)^2.$$ Aaronson and Ambainis showed that a positive answer would imply that the acceptance probability of a quantum algorithm making $T$ queries to a Boolean input can be approximated, on most inputs, by a classical algorithm making polynomially many queries in $T$ and the error parameters. A theorem of Dinur, Friedgut, Kindler and O'Donnell gives $\max_i \operatorname{Inf}_i(p) \ge \operatorname{Var}(p)^3 / 2^{O(d)}$. O'Donnell, Saks, Schramm and Servedio proved $\max_i \operatorname{Inf}_i(f) \ge \operatorname{Var}(f) / D$ for every $f : \{-1,1\}^n \to \{-1,1\}$ computed by a decision tree of depth $D$, and Montanaro proved the inequality below for block-multilinear forms of degree $k$ (each monomial takes one variable from each of $k$ blocks of $n$ variables) all of whose $n^k$ coefficients are $\pm\alpha$ for a single $\alpha$. Bhattacharya proved a version for random restrictions: if $f$ has degree $d \ge 2$, values in $[0,1]$ and $\operatorname{Var}(f) \ge 1/d$, then a random restriction of $f$ keeping each variable with probability of order $(\log d)/d$ has, with probability at least of order $\operatorname{Var}(f) (\log d)/d$, a variable of influence at least $\operatorname{Var}(f)^2 / d^{C}$, for an absolute constant $C$.
Problem. Are there absolute constants $c, C > 0$, independent of $n$, $d$ and $p$, such that every such polynomial satisfies $$\max_{1 \le i \le n} \operatorname{Inf}_i(p) \ge c \left( \frac{\operatorname{Var}(p)}{d} \right)^{C} ?$$
Source: Aaronson and Ambainis (2014; arXiv 2009), Conjecture 1.7, for polynomials with values in [0, 1]; in this normalization, Escudero Gutiérrez, Saucedo and Palazuelos (2026), Conjecture 1.2.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- FA
- Keywords
- AIM Open Applied Problems, Boolean functions, influences, quantum query complexity
References
@article{aaronson2014,
author = {Aaronson, Scott and Ambainis, Andris},
title = {The need for structure in quantum speedups},
journal = {Theory Comput.},
volume = {10},
number = {6},
year = {2014},
pages = {133--166},
doi = {10.4086/toc.2014.v010a006},
eprint = {0911.0996},
archivePrefix = {arXiv},
}
@misc{escudero2026,
author = {Escudero Guti{\'e}rrez, Francisco and Saucedo, Miquel and Palazuelos, Carlos},
title = {Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms},
year = {2026},
eprint = {2609.05201},
archivePrefix = {arXiv},
}
@article{dinur2007,
author = {Dinur, Irit and Friedgut, Ehud and Kindler, Guy and O'Donnell, Ryan},
title = {On the {F}ourier tails of bounded functions over the discrete cube},
journal = {Israel J. Math.},
volume = {160},
number = {1},
year = {2007},
pages = {389--412},
doi = {10.1007/s11856-007-0068-9},
}
@inproceedings{odonnell2005,
author = {O'Donnell, Ryan and Saks, Michael and Schramm, Oded and Servedio, Rocco A.},
title = {Every decision tree has an influential variable},
booktitle = {46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005)},
publisher = {IEEE},
year = {2005},
pages = {31--39},
doi = {10.1109/SFCS.2005.34},
}
@article{montanaro2012,
author = {Montanaro, Ashley},
title = {Some applications of hypercontractive inequalities in quantum information theory},
journal = {J. Math. Phys.},
volume = {53},
number = {12},
year = {2012},
pages = {122206},
doi = {10.1063/1.4769269},
}
@inproceedings{bhattacharya2025,
author = {Bhattacharya, Sreejata Kishor},
title = {Random restrictions of bounded low degree polynomials are juntas},
booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {325},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2025},
pages = {17:1--17:21},
doi = {10.4230/LIPIcs.ITCS.2025.17},
eprint = {2402.13952},
archivePrefix = {arXiv},
}
@misc{aim-aaronson-ambainis-influence,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Aaronson–Ambainis influential-variable conjecture}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/327-aaronson-ambainis-influence.md},
note = {Entry 327 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00324, "Aaronson–Ambainis influential-variable conjecture", clopen.solutions.