About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Computing
Paper
Polynomial threshold functions, AC0 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].