Difference between revisions of "Polynomial threshold"
(Created page with "== 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 poly...") |
(→Properties) |
||
| Line 3: | Line 3: | ||
== Properties == | == Properties == | ||
| + | * 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 14:51, 4 February 2019
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].
Properties
- TODO: proposition 5.6 in O'Donnell says that functions with small noise sensitivity are close to low degree polynomial thresholds.
- TODO
