A polynomial threshold function is a Boolean function obtained by thresholding a real polynomial 
on 
. The function is 
when 
and 
when 
.
It is said to have degree at most 
when such a representation exists with a polynomial
of total degree at most 
(O'Donnell 2021, §5.1). For example, 
is represented by 
. Taking 
of total degree at most 1
gives linear threshold functions.
Polynomial Threshold Function
See also
Average Sensitivity, Boolean Function, Linear Threshold Function, Total DegreeExplore with Wolfram|Alpha
References
O'Donnell, R. Analysis of Boolean Functions. 21 May 2021. https://arxiv.org/abs/2105.10386.Cite this as:
Weisstein, Eric W. "Polynomial Threshold Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PolynomialThresholdFunction.html