72 citations · 177 across the 7 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009★ 21 cited
Improved Approximation of Linear Threshold Functions
Ilias Diakonikolas, Rocco A. Servedio
We prove two main results on how arbitrary linear threshold functions $f(x) = \sign(w\cdot x - θ)$ over the -dimensional Boolean hypercube can be approximated by simple threshol…
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…