The Gotsman-Linial Conjecture is False

08/04/2021
by   Brynmor Chapman, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset