Fetching the paper…

Reading the bibliography…

Bounding the Sensitivity of Polynomial Threshold Functions · Around

2009

Bounding the Sensitivity of Polynomial Threshold Functions

Harsha, Prahladh, Klivans, Adam, Meka, Raghu

Original
PDF
Post on X

Understand

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of polynomial threshold functions.

More specifically, for a Boolean function f on n variables equal to the sign of a real, multivariate polynomial of total degree d we prove 1) The average sensitivity of f is at most O(n^{1-1/(4d+6)}) (we also give a combinatorial proof of the bound O(n^{1-1/2^d}).
2) The noise sensitivity of f with noise rate \delta is at most O(\delta^{1/(4d+6)}).
Previously, only bounds for the linear case were known.

Built on

Decision theoretic generalizations of the PAC model for neural net and other learning applications
1990
Earlier work this paper cites.
The polynomial method in circuit complexity
1993
Earlier work this paper cites.
Constant depth circuits, Fourier transform, and learnability
1993
Earlier work this paper cites.
Spectral properties of threshold functions
1994
Earlier work this paper cites.
Toward efficient agnostic learning
1994
Earlier work this paper cites.
Some optimal inapproximability results
1997
Earlier work this paper cites.
Gaussian Hilbert Spaces
1997
Earlier work this paper cites.

Similar

Noise sensitivity of Boolean functions and applications to percolation
1999
Cited alongside, same era.
Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
Original
2000
Cited alongside, same era.
Hardness amplification within NP
2002
Cited alongside, same era.
Algorithms with large domination ratio
2003
Cited alongside, same era.
Learning intersections and thresholds of halfspaces
2004
Cited alongside, same era.
Noise stability of weighted majority , 2004
2004
Cited alongside, same era.

Then

Every linear threshold function has a low-weight approximator
2006
Later among the works it cites.
Separating AC 0
——— · 2007
Later among the works it cites.
Learning geometric concepts via gaussian surface area
——— · 2008
Later among the works it cites.
The pattern matrix method for lower bounds on quantum communication
Original
2008
Later among the works it cites.
Average sensitivity and noise sensitivity of polynomial threshold functions , 2009
Original
2009
Closest in time.
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions , 2009
Original

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Noise sensitivity and chaos in social choice theory

2005

Cited alongside, same era.

The expressive power of voting polynomials

Cited in the paper.

Quantum lower bounds by polynomials

Cited in the paper.

Collective coin flipping, robust voting schemes and minima of Banzhaf values

Cited in the paper.

Polynomial regression under arbitrary product distributions

Cited in the paper.

Distributional and L q L^{q} norm inequalities for polynomials over convex bodies in ℝ n {\mathbb{R}}^{n}

Cited in the paper.

2009

Closest in time.

Pseudorandom generators for polynomial threshold functions , 2009

2009

Closest in time.