## Toward Attribute Efficient Learning of Decision Lists and Parities

** Adam R. Klivans, Rocco A. Servedio**; 7(Apr):587--602, 2006.

### Abstract

We consider two well-studied problems regarding attribute
efficient learning: learning
decision lists and learning parity functions.
First, we give an algorithm for learning decision
lists of length *k* over *n* variables using
*2 ^{Õ(k1/3)} log n* examples and time

*n*. This is the first algorithm for learning decision lists that has both subexponential sample complexity and subexponential running time in the relevant parameters. Our approach is based on a new construction of low degree, low weight polynomial threshold functions for decision lists. For a wide range of parameters our construction matches a lower bound due to Beigel for decision lists and gives an essentially optimal tradeoff between polynomial threshold function degree and weight.

^{Õ(k1/3)}
Second, we give an
algorithm for learning an unknown parity function on *k* out of *n*
variables using *O(n ^{1-1/k})* examples in poly

*(n)*time. For

*k=o(*log

*n)*this yields the first polynomial time algorithm for learning parity on a superconstant number of variables with sublinear sample complexity. We also give a simple algorithm for learning an unknown length-

*k*parity using

*O(k*log

*n)*examples in

*n*time, which improves on the naive

^{k/2}*n*time bound of exhaustive search.

^{k}[abs][pdf]