A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.

Nathan Segerlind Samuel R. Buss Russell Impagliazzo

Published in: SIAM J. Comput. (2004)

Keyphrases

efficient learning
lower bound
learning algorithm
upper bound
high resolution
lower and upper bounds
learning theory
boolean functions
objective function
vc dimension
branch and bound algorithm
online algorithms
machine learning
branch and bound
theoretical analysis
low resolution
online learning
np hard