The Gotsman-Linial Conjecture is False
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.
READ FULL TEXT