Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms.

Jehoshua Bruck Roman Smolensky

Published in: SIAM J. Comput. (1992)

Keyphrases

threshold functions
boolean functions
linear threshold
decision lists
low degree
agnostic learning
feature space
uniform distribution
statistical queries