Polynomial Representations of Threshold Functions and Algorithmic Applications.

Josh Alman Timothy M. Chan Ryan Williams

Published in: CoRR (2016)

Keyphrases

threshold functions
boolean functions
low degree
decision lists
linear threshold
agnostic learning
special case
sample complexity
concept classes
learning algorithm
supervised learning
model selection