← All problems

Weak Gotsman–Linial conjecture on polynomial threshold function influence

9 years old · traced to

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

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

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

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

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.

Solutions 1

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.See full solutionHide full solution