CaltechAUTHORS
  A Caltech Library Service

Polynomial Threshold Functions, AC^0 Functions and Spectral Norms

Bruck, Jehoshua and Smolensky, Roman (1990) Polynomial Threshold Functions, AC^0 Functions and Spectral Norms. In: 1990 31st Annual Symposium on Foundations of Computer Science, Proceedings. IEEE Computer Society Press , Los Alamitos, CA, pp. 632-641. ISBN 0-8186-2082-X http://resolver.caltech.edu/CaltechAUTHORS:20120425-065829076

[img]
Preview
PDF - Published Version
See Usage Policy.

522Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120425-065829076

Abstract

The class of polynomial-threshold functions is studied using harmonic analysis, and the results are used to derive lower bounds related to AC^0 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 L_1 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 AC^0 functions are derived.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/FSCS.1990.89585DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=89585PublisherUNSPECIFIED
Additional Information:© 1990 IEEE. Date of Current Version: 06 August 2002. We thank Noga Alon for his useful observations that greatly improved this paper and to Chaim Gotsman and Sunny Siu for their comments on an early draft of this paper.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number3908543
Record Number:CaltechAUTHORS:20120425-065829076
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20120425-065829076
Official Citation:Bruck, J.; Smolensky, R.; , "Polynomial threshold functions, AC functions and spectrum norms," Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on , vol., no., pp.632-641 vol.2, 22-24 Oct 1990 doi: 10.1109/FSCS.1990.89585 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=89585&isnumber=2915
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:30356
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:25 Apr 2012 17:15
Last Modified:26 Dec 2012 15:08

Repository Staff Only: item control page