Polynomial threshold functions, AC functions and spectrum norms

By Jehoshua Bruck, R. Smolensky. 1990

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.<<ETX>>

Subfields: Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

1. Zeyuan Allen-Zhu
2. Yuanzhi Li
3. Tengyu Ma
4. Ohad Shamir
5. Gilad Yehudai
6. Quanquan Gu
7. Jason D. Lee

In Algorithms & Complexity

1. Zeyuan Allen-Zhu
2. Yuanzhi Li

Citations in the corpus

• Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “The lower bound for the classification accuracy using low-degree polynomials has been widely studied as the (approximate) threshold degree of a function or the sign-rank of a matrix [18, 21, 25, 41, 75, 81].”