Class Description

PT1: Polynomial Threshold Functions

The class of Boolean functions f:{-1,1}n->{-1,1} such that f(x)=sgn(p(x)), where p is a polynomial having a number of terms polynomial in n.

Defined in [BS90], where it was also shown that PT1 contains PL1 (and this inclusion is strict), and that PT1 is contained in PL (and this inclusion is strict).

Linked From

PL1: Polynomially-Bounded L1 Spectral Norm

The class of Boolean functions f:{-1,1}n->{-1,1} such that the sum of absolute values of Fourier coefficients of f is bounded by a polynomial in n.

Defined in [BS90], where it was also shown that PL1 is contained in PT1 (and this inclusion is strict).

More about...


PL: Polynomially-Bounded L-1 Spectral Norm

The class of Boolean functions f:{-1,1}n->{-1,1} such that the maximum of |α|-1, over all Fourier coefficients α of f, is upper-bounded by a polynomial in n.

Defined in [BS90], where it was also shown that PL contains PT1 (and this inclusion is strict).

More about...