Polynomial threshold functions, AC⁰ functions, and spectral norms

Abstract

This paper examines the class of polynomial threshold functions using harmonic analysis and applies the results to derive lower bounds related to AC0 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 teams). 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 L1 spectral norm is bounded by a polynomial in n is a polynomial threshold function, while a Boolean function whose L10-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 AC0 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].