Name
Abstract | ||
|---|---|---|
The class of polynomial-threshold functions is studied using harmonic analysis, and the results are used to derive lower bounds related to AC/sup 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/sub 1/ spectral norm is bounded by a polynomial in n is a polynomial-threshold function, and that a Boolean function whose L/sub infinity //sup -1/ spectral norm is not bounded by a polynomial in n is not a polynomial-threshold function. Some results for AC/sup 0/ functions are derived. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1137/0221003 | SFCS '90 Proceedings of the 31st Annual Symposium on Foundations of Computer Science |
Keywords | DocType | Volume |
polynomial threshold function,ac0 function,spectral norm,boolean functions,lower bound,neural networks,spectrum,computational modeling,polynomials,boolean function,circuits,harmonic analysis | Journal | 21 |
Issue | ISSN | ISBN |
1 | 0097-5397 | 0-8186-2082-X |
Citations | PageRank | References |
37 | 5.37 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jehoshua Bruck | 1 | 3256 | 374.15 |
| Roman Smolensky | 2 | 118 | 14.12 |