Polynomial Threshold Functions, AC^0 Functions and Spectral Norms
- Creators
-
Bruck, Jehoshua
- Smolensky, Roman
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.
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.Attached Files
Published - BRUfocs90.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:f7fef0aa83b16f661ab023c5a7762fe4
|
534.8 kB | Preview Download |
Additional details
- Eprint ID
- 30356
- Resolver ID
- CaltechAUTHORS:20120425-065829076
- Created
-
2012-04-25Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 3908543