%0 Journal Article
%T The Average Sensitivity of an Intersection of Half Spaces
%A Daniel M. Kane
%J Mathematics
%D 2013
%I arXiv
%X We prove new bounds on the average sensitivity of the indicator function of an intersection of $k$ halfspaces. In particular, we prove the optimal bound of $O(\sqrt{n\log(k)})$. This generalizes a result of Nazarov, who proved the analogous result in the Gaussian case, and improves upon a result of Harsha, Klivans and Meka. Furthermore, our result has implications for the runtime required to learn intersections of halfspaces.
%U http://arxiv.org/abs/1309.2987v3