Average sensitivity and noise sensitivity of polynomial threshold functions

Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio +1

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs). These bounds hold both for PTFs ove…