# Polynomial threshold

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))$.