Approximating Linear Threshold Predicates.

Mahdi Cheraghchi Johan Håstad Marcus Isaksson Ola Svensson

Published in: APPROX-RANDOM (2010)

Keyphrases

linear threshold
boolean functions
sampling algorithm
learning algorithm
sample complexity
concept classes
mistake bound
winnow algorithm
perceptron algorithm
noise tolerant
decision trees
small number