The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions
Daniel M. Kane · 2010
We prove asymptotically optimal bounds on the Gaussian noise sensitivity of degree-d polynomial threshold functions. These bounds translate into optimal bounds on the Gaussian surface area of such functions, and therefore imply new bounds on the running time of agnostic learning algorithms.