The superweak Gotsman–Linial conjecture

The conjecture asks for a polylogarithmic improvement over square-root growth of average sensitivity for every fixed-degree polynomial threshold function. Gotsman and Linial proposed the stronger $O(d\sqrt n)$ bound; the superweak form follows from Kane’s later estimate.

Known results

• Kane, 2009: $\mathbf{AS}[f]\leq 2^{O(d)}\log n\,n^{1-1/(4d+2)}$.
• Kane, 2012: $\mathbf{AS}[f]\leq \sqrt n(\log n)^{O(d\log d)}2^{O(d^{2}\log d)}$, which has the required superweak form for fixed $d$.
• Chapman, 2017 and 2021: counterexamples to the stronger extremal Gotsman–Linial conjecture, not to the superweak bound.

2026 literature check

A 2026 paper reproduces Kane’s bound but says that some weaker versions of the Gotsman–Linial conjecture remain open; it does not identify the stated superweak formulation as unresolved.

Current status (as of September 2026): Kane’s cited bound settles the stated superweak form for each fixed $d$, but this remains a claimed result in this report; the stronger $O(d\sqrt n)$ conjecture is open.