Average sensitivity of polynomial threshold functions

Proves that a degree-at-most-d polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most 8d\sqrt n, uniformly for 1\le d\le n. Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with \mathop{\mathrm{sign}}\nolimits (0)=1. (Lean)

Manuscript

Average sensitivity of polynomial threshold functions

September 25, 2026 · source · Lean formalization available · cite as \cite{OAI:Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026}

For every n ≥ 1 and 1\le d\le n, we prove that a polynomial threshold function of degree at most d on the uniform Boolean cube has average sensitivity at most 8d\sqrt n. This proves the asymptotic form of the Gotsman–Linial conjecture. The bound is uniform in both parameters and uses the convention \mathop{\mathrm{sgn}}\nolimits (0)=1.

Result 127 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.