Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract)

Jehoshua Bruck Roman Smolensky

Published in: FOCS (1990)

Keyphrases

extended abstract
threshold functions
boolean functions
low degree
decision lists
linear threshold
agnostic learning
linear classifiers
target function
decision trees
training set
active learning
support vector machine