Weak Gotsman–Linial conjecture on polynomial threshold function influence

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.

Sources & referencesView supporting material

Primary source

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 0

No solutions have been posted yet.