Theory of Computing ------------------- Title : Bounding the Sensitivity of Polynomial Threshold Functions Authors : Prahladh Harsha, Adam Klivans, and Raghu Meka Volume : 10 Number : 1 Pages : 1-26 URL : https://theoryofcomputing.org/articles/v010a001 Abstract -------- We give the first nontrivial upper bounds on the average sensitivity and noise sensitivity of polynomial threshold functions. More specifically, for a Boolean function $f$ on $n$ variables equal to the sign of a real, multivariate polynomial of total degree $d$, we prove * The average sensitivity of $f$ is at most $O(n^{1-1/(4d+6)})$. (We also give a combinatorial proof of the bound $O(n^{1-1/2^d})$.) * The noise sensitivity of $f$ with noise rate $\delta$ is at most $O(\delta^{1/(4d+6)})$. Previously, only bounds for the degree $d = 1$ case were known ($O(\sqrt{n}$) and $O(\sqrt{\delta})$, for average and noise sensitivity, respectively). We highlight some applications of our results in learning theory where our bounds immediately yield new agnostic learning algorithms and resolve an open problem of Klivans, O'Donnell and Servedio (FOCS'08). The proof of our results use (i) the invariance principle of Mossel, O'Donnell and Oleszkiewicz (2010), (ii) the anti-concentration properties of polynomials in Gaussian space due to Carbery and Wright (2001) and (iii) new structural theorems about random restrictions of polynomial threshold functions obtained via hypercontractivity. These structural results may be of independent interest, as they provide a generic template for transforming problems related to polynomial threshold functions defined on the Boolean hypercube to polynomial threshold functions defined in Gaussian space. An extended abstract (http://dx.doi.org/10.1145/1806689.1806763) of this result, which was proved independently by two groups (the authors of this paper and Diakonikolas et al.), appeared in the Proc. 42nd ACM Symposium on Theory of Computing, 2010.