most citedAverage sensitivity and noise sensitivity of polynomial threshold functions

11 citations · 11 across the 1 of their papers we have counts for

collaborators

1 paper

cs.CC2009★ 11 cited

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- polynomial threshold functions (PTFs). These bounds hold both for PTFs ove…