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