The limiting 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 fn,1f^*_{n,1} be the symmetric degree-one candidate defined by the monic polynomial with its root at the integer closest to 00 of parity opposite to nn, and let AS[f]\mathbf{AS}[f] denote average sensitivity.

Limiting Gotsman–Linial conjecture. The average sensitivity satisfies

AS[f]dAS[fn,1].\mathbf{AS}[f]\leq d\,\mathbf{AS}[f^*_{n,1}].

The paper presents this as a revised conjecture after refuting the exact Gotsman–Linial maximization claim. It would imply the remaining cases discussed there, but the supplied text gives no resolution.

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.