Polynomial Threshold Functions, AC⁰ Functions, and Spectral Norms

This paper examines the class of polynomial threshold functions using harmonic analysis and applies the results to derive lower bounds related to AC⁰ functions. A Boolean function is polynomial threshold if it can be represented as the sign of a sparse polynomial (one that consists of a polynomial number of terms). The main result of this paper is that the class of polynomial threshold functions can be characterized using their spectral representation. In particular, it is proved that an n-variable Boolean function whose L₁ spectral norm is bounded by a polynomial in n is a polynomial threshold function, while Boolean function whose L_∞ - 1 spectral norm is not bounded by a polynomial in n is not a polynomial threshold function [J. Bruck, SIAM J. Discrete Math., 3 (1990), pp. 168–177]. The motivation is that the characterization of polynomial threshold functions can be applied to obtain upper and lower bounds on the complexity of computing with networks of linear threshold elements. In this paper results related to the complexity of computing AC⁰ functions are presented. More applications of the characterization theorem are presented in [J. Bruck, SIAM J. Discrete Math., 3 (1990), pp. 168–177] and [K. Y. Siu and J. Bruck, SIAM J. Discrete Math., 4 (1991), pp. 423–435].