The Average Sensitivity of an Intersection of Half Spaces

Daniel M. Kane

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)})$. Th…