Fetching the paper…
Reading the bibliography…
We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs).
An introduction to probability theory and its applications
W. Feller · 1968
Earlier work this paper cites.
The influence of variables on boolean functions
J. Kahn, G. Kalai, and N. Linial · 1988
Earlier work this paper cites.
Constant depth circuits, Fourier transform and learnability
N. Linial, Y. Mansour, and N. Nisan · 1993
Earlier work this paper cites.
Spectral properties of threshold functions
C. Gotsman and N. Linial · 1994
Earlier work this paper cites.
On the Fourier spectrum of monotone functions
N. Bshouty and C. Tamon · 1996
Earlier work this paper cites.
Influences of variables and threshold intervals under group symmetries
J. Bourgain and G. Kalai · 1997
Earlier work this paper cites.
Gaussian Hilbert Spaces
S. Janson · 1997
Earlier work this paper cites.
Gaussian measures
V. Bogachev · 1998
Earlier work this paper cites.
Boolean functions with low average sensitivity depend on few coordinates
E. Friedgut · 1998
Earlier work this paper cites.
Noise sensitivity of Boolean functions and applications to percolation
I. Benjamini, G. Kalai, and O. Schramm · 1999
Earlier work this paper cites.
Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of boolean variables
Y. Shi · 2000
Earlier work this paper cites.
Distributional and L q L^{q} norm inequalities for polynomials over convex bodies in R n R^{n}
A. Carbery and J. Wright · 2001
Earlier work this paper cites.
Learnability beyond A C 0 {AC^{0}}
J. Jackson, A. Klivans, and R. Servedio · 2002
Cited alongside, same era.
On the noise sensitivity of monotone functions
E. Mossel and R. O’Donnell · 2003
Cited alongside, same era.
Learning intersections and thresholds of halfspaces
A. Klivans, R. O’Donnell, and R. Servedio · 2004
Cited alongside, same era.
Noise stability of weighted majority, 2004
Y. Peres · 2004
Cited alongside, same era.
Noise stability of functions with low influences: invariance and optimality
E. Mossel, R. O’Donnell, and K. Oleszkiewicz · 2005
Cited alongside, same era.
Lecture 4
E. Mossel · 2005
Cited alongside, same era.
Every decision tree has an influential variable
Agnostically learning decision trees
P. Gopalan, A. Kalai, and A. Klivans · 2008
Later among the works it cites.
Agnostically learning halfspaces
A. Kalai, A. Klivans, Y. Mansour, and R. Servedio · 2008
Later among the works it cites.
On agnostic boosting and parity learning
A. Kalai, Y. Mansour, and E. Verbin · 2008
Later among the works it cites.
Learning geometric concepts via Gaussian surface area
A. Klivans, R. O’Donnell, and R. Servedio · 2008
Later among the works it cites.
The Chow Parameters Problem
R. O’Donnell and R. Servedio · 2008
Later among the works it cites.
Randomly supported independence and resistance
Per Austrin and Johan Håstad · 2009
Closest in time.
Bounded independence fools halfspaces
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
R. O’Donnell, M. Saks, O. Schramm, and R. Servedio · 2005
Cited alongside, same era.
On the fourier tails of bounded functions over the discrete cube
Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell · 2006
Cited alongside, same era.
Lecture 16: The hypercontractivity theorem
R. O’Donnell · 2007
Cited alongside, same era.
Learning monotone decision trees in polynomial time
R. O’Donnell and R. Servedio · 2007
Cited alongside, same era.
Every linear threshold function has a low-weight approximator
R. Servedio · 2007
Cited alongside, same era.
Polynomial regression under arbitrary product distributions
E. Blais, R. O’Donnell, and K. Wimmer · 2008
Cited alongside, same era.
I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, and E. Viola · 2009
Closest in time.
Improved approximation of linear threshold functions
I. Diakonikolas and R. Servedio · 2009
Closest in time.
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
I. Diakonikolas, R. Servedio, L.-Y. Tan, and A. Wan · 2009
Closest in time.
Learning threshold-of- a c 0 ac^{0} circuits
P. Gopalan and R. Servedio · 2009
Closest in time.
Bounding the sensitivity of polynomial threshold functions
P. Harsha, A. Klivans, and R. Meka · 2009
Closest in time.
Agnostically learning halfspaces with margin errors
S. Shalev Shwartz, O. Shamir, and K. Sridharan · 2009
Closest in time.