The superweak Gotsman–Linial conjecture

Let f:{1,1}n{1,1}f:\{-1,1\}^n\to\{-1,1\} be an (n,d)(n,d)-PTF, meaning the sign of a real polynomial of degree at most dd on the Boolean hypercube. Let AS[f]\mathbf{AS}[f] denote its average sensitivity.

Superweak Gotsman–Linial conjecture. For some function gg depending only on dd,

AS[f]O(nlogg(d)n).\mathbf{AS}[f]\in O\left(\sqrt n\log^{g(d)}n\right).

Daniel Kane resolved this conjecture. It is weaker than the O(dn)O(d\sqrt n) asymptotic bound and was introduced as a still useful consequence for applications.

Sources & referencesView supporting material

Primary source

Brynmor Chapman, “The Gotsman-Linial Conjecture is False”, arXiv:2108.02288 (2021).

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.