The Correct Exponent for the Gotsman-Linial Conjecture

Abstract

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 $\sqrt{n}(\log (n){)}^{O(d\log (d))}{2}^{O(d^2\log (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 $\Theta (d\sqrt{n})$.

References in corpus (1)

• A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

Cited by in corpus (1)

• Social choice, computational complexity, Gaussian geometry, and Boolean functions