Bounding the sensitivity of polynomial threshold functions
Prahladh Harsha, Adam R. Klivans, Raghu Meka · 2009
We give the first non-trivial 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(n1−1/(4d+3) () (we also give a simple combinatorial proof of the bound O n1−1/2d)). • the noise sensitivity of f with noise rate δ is at most O(δ 1/(4d+6)). Previously, only bounds for the degree d = 1 case were known (O ( √ n) and O ( √ δ), 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 et al. The proof of our results use (i) the in principle of Mossel et al. and Mossel, (ii) the anticoncentration properties of polynomials in Gaussian space due to Carbery and Wright 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