The Correct Exponent for the Gotsman-Linial Conjecture

Daniel M. Kane

We prove a new bound on the average sensitivity of polynomial threshold functions. In particular we show that a polynomial threshold function of degree $d$ in at most $n$ variables…