Let f:-1,1^n→-1,1 be a degree-d polynomial threshold function, and let operatornamemathbfI[f] denote its total influence. Weak Gotsman–Linial conjecture. For any degree-d threshold function f on n variables, operatornamemathbfI[f]≤ O(d√n). This is a relaxation of the refuted exact Gotsman–Linial maximizer conjecture: for d<√ n, the conjectured symmetric bound has order Theta(d√ n), and the weaker asymptotic upper bound remains the relevant question in the paper.

Weak Gotsman–Linial conjecture on polynomial threshold function influence

About 9 years old · traced to 2017

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a degree- $d$ polynomial threshold function, and let $\operatorname{\mathbf{I}}[f]$ denote its total influence. Weak Gotsman–Linial conjecture. For any degree- $d$ threshold function $f$ on $n$ variables,

\operatorname{\mathbf{I}}[f]\le O(d\sqrt{n}).

This is a relaxation of the refuted exact Gotsman–Linial maximizer conjecture: for $d<\sqrt n$ , the conjectured symmetric bound has order $\Theta(d\sqrt n)$ , and the weaker asymptotic upper bound remains the relevant question in the paper.

References

Primary source

Hyo Won Kim, Chris Maldonado and Jake Wellens, “On Graphs and the Gotsman-Linial Conjecture for d = 2”, arXiv:1709.06650 (2017).

asymptotic-combinatorics boolean-function-influence polynomial-threshold-functions

Posted 1 month ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

RemarkAI-assistedClaimed by OpenAI. For every polynomial threshold function on the uniform n-dimensional Boolean cube with 1 <= d <= n, the manuscript claims total influence, equivalently average sensitivity, at most 8dsqrt(n). This addresses the page’s weak Gotsman–Linial order bound. It does not assert the refuted exact symmetric-maximizer formulation or an optimal leading constant.See full solutionHide full solution

Claimed by OpenAI. For every polynomial threshold function on the uniform n-dimensional Boolean cube with 1 <= d <= n, the manuscript claims total influence, equivalently average sensitivity, at most 8dsqrt(n). This addresses the page’s weak Gotsman–Linial order bound. It does not assert the refuted exact symmetric-maximizer formulation or an optimal leading constant.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf

OpenAI-127-01-Average-sensitivity-of-polynomial-threshold-functions.pdf354,487 bytesOpen