Toward Attribute Efficient Learning Algorithms

Adam R. Klivans, Rocco A. Servedio

We make progress on two important problems regarding attribute efficient learnability. First, we give an algorithm for learning decision lists of length $k$ over $n$ variables usin…