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.