# Polynomial threshold

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Definition

A function $f:\{-1,1\}^n \to \{-1,1\}$ is called a polynomial threshold function of degree at most $k$ if there exists a real polynomial $p(x)$ of degree at most $k$ such that $f(x) = \mathrm{sign}(p(x))$.

The special case $k = 1$ is of special interest; it is the linear threshold function.

## Properties

• The total influence of a degree-$k$ polynomial threshold function is bounded by $2^{O(d)}O(n^{1-1/(4k+6)})$. [1]
• The noise sensitivity of a degree-$k$ polynomial threshold function, when the noise is of rate $\delta$, is at most $2^{O(d)}O(\delta^{1/(4k+6)})$. [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

1. Prahladh Harsha, Adam Klivans, Raghu Meka, Bounding the Sensitivity of Polynomial Threshold Functions, Theorem 1.6
2. Prahladh Harsha, Adam Klivans, Raghu Meka, Bounding the Sensitivity of Polynomial Threshold Functions, Theorem 1.3