The asymptotic Gotsman–Linial conjecture

Let $f:\{-1,1\}^n\to\{-1,1\}$ be an $(n,d)$-PTF, meaning the sign of a real polynomial of degree at most $d$ on the Boolean hypercube. Let $\mathbf{AS}[f]$ denote its average sensitivity.

Asymptotic Gotsman–Linial conjecture. There is an upper bound

$$\mathbf{AS}[f]\in O(d\sqrt n).$$

Daniel Kane resolved this conjecture. The paper distinguishes it from the stronger exact maximization conjecture and notes that this asymptotic form is sufficient for many of the intended complexity-theoretic and learning-theoretic applications.