72 citations · 241 across the 15 of their papers we have counts for
3 papers · 2 filters
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…
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…
Bounded Independence Fools Halfspaces
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal +2
We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps) /\eps^2). Up to logarithmic factors, our result…