The Correct Exponent for the Gotsman-Linial Conjecture

Original · EN

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 has average sensitivity at most √n((n))O(d(d))2O(d²(d). For fixed d the exponent in terms of n in this bound is known to be optimal. This bound makes significant progress towards the Gotsman-Linial Conjecture which would put the correct bound at Θ(d√n).