We study the problem of learning parity functions that depend on at most k variables (k-parities) attribute-efficiently in the mistake-bound model.
We design simple, deterministic, polynomial-time algorithms for learning k-parities with mistake bound O(n^{1-\frac{c}{k}}), for any constant c > 0. These are the first polynomial-time algorithms that learn \omega(1)-parities in ... more >>>