The limiting Gotsman–Linial conjecture
The limiting Gotsman–Linial conjecture
Let be an -PTF, meaning the sign of a real polynomial of degree at most on the Boolean hypercube. Let be the symmetric degree-one candidate defined by the monic polynomial with its root at the integer closest to of parity opposite to , and let denote average sensitivity.
Limiting Gotsman–Linial conjecture. The average sensitivity satisfies
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.