Title :
The Correct Exponent for the Gotsman-Linial Conjecture
Author_Institution :
Dept. of Math., Stanford Univ., Stanford, CA, USA
Abstract :
We prove new bounds on the average sensitivity of polynomial threshold functions. In particular, we show the average sensitivity of a polynomial threshold function of constant degree is not much more than the square root of the dimension of its space of definition. This bound amounts to a significant improvement over previous bounds, and in particular, for fixed degree provides the correct asymptotic exponent in the dimension.
Keywords :
polynomials; Gotsman-Linial conjecture; function sensitivity; polynomial threshold function; Atmospheric measurements; Hypercubes; Polynomials; Reactive power; Sensitivity; Standards; Combinatorial Mathematics; Polynomials;
Conference_Titel :
Computational Complexity (CCC), 2013 IEEE Conference on
Conference_Location :
Stanford, CA
DOI :
10.1109/CCC.2013.15
