The Aaronson-Ambainis conjecture asserts that a bounded low-degree polynomial on the Boolean cube with appreciable variance has an
influential coordinate (Aaronson and Ambainis 2014). In the 
convention, take 
and let ![f:{-1,1}^n->[-1,1]](/images/equations/Aaronson-AmbainisConjecture/Inline3.svg)
have degree at most 
. The degree is the total
degree of the unique multilinear polynomial representing
. If 
has the discrete
uniform distribution on the cube and 
reverses coordinate 
, the coordinate influence is
![I_i(f)=1/4E[(f(X)-f(X^({i})))^2],](/images/equations/Aaronson-AmbainisConjecture/NumberedEquation1.svg) |
where 
denotes the expectation value. The sum
of the coordinate influences is the total influence.
The conjecture asks for a lower bound on 
that is a fixed positive power of 
, up to an absolute constant. Here ![Var(f)=E[f(X)^2]-E[f(X)]^2](/images/equations/Aaronson-AmbainisConjecture/Inline12.svg)
is the variance
of 
under the discrete uniform distribution
on the cube.
Turturean (2026) reports the bound
 |
A nonpublic Anthropic model in a research system developed at Physical Superintelligence generated the proof and its Lean formalization. The project reports Lean and Nanoda checks of the influence statements (Physical Superintelligence 2026). Blanc et al. (2026) present a weaker quantitative bound in an exposition of Turturean's proof.
The influence bound has an application to query complexity. For a decision procedure with quantum access to its input bits,
a deterministic classical algorithm can approximate
its acceptance probability on at least a fraction
of inputs under the discrete uniform
distribution, for fixed error tolerance and fixed 
. The number of queries is polynomial
in the quantum query complexity (Aaronson and
Ambainis 2014).
