72 citations · 399 across the 60 of their papers we have counts for
4 papers · 1 filter
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…
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan +1
We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube {-1,1}^n. This result shows that every degree-d PTF can be decomposed into a c…
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…