The limiting Gotsman–Linial conjecture

About 5 years old · traced to

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,1∗f^*_{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]≤d AS[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.

References

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.