Toward Attribute Efficient Learning Algorithms
  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 using $2^{\tilde{O}(k^{1/3})} \log n$ examples and time
$n^{\tilde{O}(k^{1/3})}$. 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 establishes a relationship
between attribute efficient learning and polynomial threshold functions and 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 1994 lower bound due to Beigel for the ODDMAXBIT predicate and gives
an essentially optimal tradeoff between polynomial threshold function degree
and weight.
  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 time polynomial in $n$.
For $k=o(\log n)$ this yields a polynomial time algorithm with sample
complexity $o(n)$. This is the first polynomial time algorithm for learning
parity on a superconstant number of variables with sublinear sample complexity.
