# Polynomial threshold

## 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 total influence 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.

## Conjectures

- Gotsman and Linial [13] conjectured, for example,that the average sensitivity of a degree-dpolynomial isO(d√n). (TODO: this is from Harsha at el paper, please cite properly, just here for keepsies)

## 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