Aaronson-Ambainis conjecture

Workshop introduction

We fix some notation. For all $n\ge 1$, any function $f:\{-1,1\}^n\to \mathbb{R}$ has the unique Fourier expansion \begin{equation*} f=\sum_{S\subset [n]}\widehat{f}(S)\chi_S \end{equation*} where for each $S\subset [n]:=\{1,\dots, n\}$, $\widehat{f}(S)\in\mathbb{R}$ and $\chi_S(x):=\prod_{j\in S}x_j$. The degree of $f$ is the maximal $|S|$ for which $\widehat{f}(S)\neq 0$. For $d\ge 1$, $f$ is $d$-homogeneous in case it is a linear combination of $\chi_S,|S|=d$. The variance of $f$ is \begin{equation*} \text{Var}(f)=\sum_{S\neq \emptyset}\widehat{f}(S)^2. \end{equation*} For $1\le j\le n$, the influence of $j$-th variable of $f$ is defines as \begin{equation*} \text{Inf}j(f):=\sum{j\in S}\widehat{f}(S)^2. \end{equation*} We always equip $\{-1,1\}^n$ with the uniform probability measure and denote by $\|\cdot\|_p$ the corresponding $L_p$-norm, $1\le p\le \infty$. For $1\le j\le n$, denote \begin{equation*} D_j f(x):=\frac{f(x)-f(x^{\oplus j})}{2}, \end{equation*} where $f(x^{\oplus j}):=f(x_1,\dots, x_{j-1}, -x_j,x_{j+1},\dots, x_n)$. Note that $D_j^2=D_j$. The heat semigroup on $\{-1,1\}^n$ is $P_t=e^{-t\Delta}$ with $\Delta=\sum_{j=1}^{n}D_j$. The sensitivity of $f$ at $x\in\{-1,1\}^n$ is defined as \begin{equation*} s(f,x):=\sharp {1\le j\le n: f(x)\neq f(x^{\oplus j})}, \end{equation*} and the sensitivity of $f$ is \begin{equation*} s(f):=\max{s(f,x):x\in{-1,1}^n}. \end{equation*} Similarly, the block sensitivity $bs(f,x)$ of $f$ at $x$ is the maximum number of disjoint subsets $B_1,\dots, B_k$ of $[n]$ such that $f(x)\neq f(x^{\oplus B_j})$ for all $1\le j \le k$, where $x^{\oplus B}$ denotes the input that flips the values in $B\subset [n]$. The block sensitivity $bs(f)$ of $f$ is then defined as $\max\{bs(f,x):x\in\{-1,1\}^n\}$.

Section context

Here we collect some problems related to the Aaronson-Ambainis Conjecture.

Dated source record, inspected 2026-09-10. Current status has not been independently reassessed. Source-reported results have not been independently verified.

Status note in the source

Some partial cases have been known. For example, it is true when

• the function $f$ is symmetric;

• the function $f$ is Boolean i.e., it takes values in $\{-1,1\}$;

• the constant $\deg(f)$ is replaced by $e^{\deg(f)}$.