DocumentCode
2834069
Title
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions
Author
Kane, Daniel M.
Author_Institution
Dept. of Math., Harvard Univ., Cambridge, MA, USA
fYear
2010
fDate
9-12 June 2010
Firstpage
205
Lastpage
210
Abstract
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.
Keywords
Gaussian noise; optimisation; polynomials; Gaussian noise sensitivity; agnostic learning algorithms; degree-d polynomial threshold functions; gaussian surface area; noise sensitivity; optimal bounds; Computational complexity; Density measurement; Gaussian distribution; Gaussian noise; Gaussian processes; Mathematics; Noise measurement; Polynomials; Random variables; Switches; Gaussian noise; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
Conference_Location
Cambridge, MA
ISSN
1093-0159
Print_ISBN
978-1-4244-7214-7
Electronic_ISBN
1093-0159
Type
conf
DOI
10.1109/CCC.2010.27
Filename
5497886
Link To Document