Difference between revisions of "Polynomial threshold"
(→Properties) |
|||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
A function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is called a '''polynomial threshold function''' of degree at most <math>k</math> if there exists a real polynomial <math>p(x)</math> of degree at most <math>k</math> such that <math>f(x) = \mathrm{sign}(p(x))</math>. | A function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is called a '''polynomial threshold function''' of degree at most <math>k</math> if there exists a real polynomial <math>p(x)</math> of degree at most <math>k</math> such that <math>f(x) = \mathrm{sign}(p(x))</math>. | ||
| + | |||
| + | The special case <math>k = 1</math> is of special interest; it is the [[linear threshold]] function. | ||
== Properties == | == Properties == | ||
| + | * The average sensitivity of a degree-<math>k</math> polynomial threshold function is bounded by <math>2^{O(d)}O(n^{1-1/(4k+6)})</math>. <ref>Prahladh Harsha, Adam Klivans, Raghu Meka, [http://theoryofcomputing.org/articles/v010a001/v010a001.pdf Bounding the Sensitivity of Polynomial Threshold Functions], Theorem 1.6</ref> | ||
| + | * The noise sensitivity of a degree-<math>k</math> polynomial threshold function, when the noise is of rate <math>\delta</math>, is at most <math>2^{O(d)}O(\delta^{1/(4k+6)})</math>. <ref>Prahladh Harsha, Adam Klivans, Raghu Meka, [http://theoryofcomputing.org/articles/v010a001/v010a001.pdf Bounding the Sensitivity of Polynomial Threshold Functions], Theorem 1.3</ref> | ||
* TODO: proposition 5.6 in O'Donnell says that functions with small noise sensitivity are close to low degree polynomial thresholds. | * TODO: proposition 5.6 in O'Donnell says that functions with small noise sensitivity are close to low degree polynomial thresholds. | ||
* TODO | * TODO | ||
| − | |||
== References == | == References == | ||
<references/> | <references/> | ||
Revision as of 10:10, 29 October 2020
Definition
A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called a polynomial threshold function of degree at most [math]k[/math] if there exists a real polynomial [math]p(x)[/math] of degree at most [math]k[/math] such that [math]f(x) = \mathrm{sign}(p(x))[/math].
The special case [math]k = 1[/math] is of special interest; it is the linear threshold function.
Properties
- The average sensitivity of a degree-[math]k[/math] polynomial threshold function is bounded by [math]2^{O(d)}O(n^{1-1/(4k+6)})[/math]. [1]
- The noise sensitivity of a degree-[math]k[/math] polynomial threshold function, when the noise is of rate [math]\delta[/math], is at most [math]2^{O(d)}O(\delta^{1/(4k+6)})[/math]. [2]
- TODO: proposition 5.6 in O'Donnell says that functions with small noise sensitivity are close to low degree polynomial thresholds.
- TODO
References
- ↑ Prahladh Harsha, Adam Klivans, Raghu Meka, Bounding the Sensitivity of Polynomial Threshold Functions, Theorem 1.6
- ↑ Prahladh Harsha, Adam Klivans, Raghu Meka, Bounding the Sensitivity of Polynomial Threshold Functions, Theorem 1.3
