We study the problem of learning parity functions that depend on at most k variables (kparities) attribute-efficiently in the mistake-bound model. We design a simple, deterministic, polynomial-time algorithm for learning k-parities with mistake bound O(n1− k c ), for any constant c > 0. This is the first polynomial-time algorithms that learns ω(1)-parities in the mistake-bound model with mistake bound o(n). Using the standard conversion techniques from the mistake-bound model to the PAC model, our algorithm can also be used for learning k-parities in the PAC model. In particular, this implies a slight improvement on the results of Klivans and Servedio [KS04] for learning k-parities in the PAC model. We also show that the Oe(nk/2) time algorithm from [KS04] that PAC-learns k-parities with optimal sample complexity can be extended to the mistake-bound model.

, ,
Dagstuhl Seminar Proceedings
Algebraic Methods in Computational Complexity 2009
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Buhrman, H., Garcia Soriano, D., & Matsliah, A. (2010). Learning parities in the mistake-bound model. In Dagstuhl Seminar Proceedings. doi:10.4230/DagSemProc.09421.5