Polynomial threshold functions, AC⁰ functions and spectral norms

Abstract

The class of polynomial-threshold functions is studied using harmonic analysis, and the results are used to derive lower bounds related to AC0 functions. A Boolean function is polynomial threshold if it can be represented as a sign function of a sparse polynomial (one that consists of a polynomial number of terms). The main result is that polynomial-threshold functions can be characterized by means of their spectral representation. In particular, it is proved that a Boolean function whose L1 spectral norm is bounded by a polynomial in n is a polynomial-threshold function, and that a Boolean function whose L∞-1 spectral norm is not bounded by a polynomial in n is not a polynomial-threshold function. Some results for AC0 functions are derived.