Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Ido Ben-Eliezer Shachar Lovett Ariel Yadin

Published in: CoRR (2009)

Keyphrases

threshold functions
low degree
linear threshold
agnostic learning
decision lists
machine learning
lower bound
boolean functions
training data
optimal solution
noisy data
uniform distribution