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

## Properties

- TODO: proposition 5.6 in O'Donnell says that functions with small noise sensitivity are close to low degree polynomial thresholds.
- TODO