Class Description

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

Linked From

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

More about...