All reports by Author David García-Soriano:

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García-Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

Harry Buhrman, David García-Soriano, Arie Matsliah

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 >>>