Revised: November 11, 2013

Published: March 25, 2014

**Keywords:**polynomial threshold function, average sensitivity

**Categories:**complexity theory, polynomials - multivariate, threshold, polynomial threshold, sensitivity, average sensitivity, special issue, Boolean special issue

**ACM Classification:**F.1.3

**AMS Classification:**68Q17

**Abstract:**
[Plain Text Version]

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)})$.

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 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 Symp. on Theory of Computing, 2010.