The Gotsman-Linial Conjecture is False
Brynmor Chapman · Society for Industrial and Applied Mathematics eBooks · 2018
In 1991, Craig Gotsman and Nathan Linial conjectured that for all n and d, the average sensitivity of a degree-d polynomial threshold function on n variables is maximized by the degree-d symmetric polynomial which computes the parity function on the d layers of the hypercube with Hamming weight closest to n/2. We refute the conjecture for almost all d and for almost all n, and we confirm the conjecture in many of the remaining cases.