2026-07-21T23:46:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2417 2024-03-06T11:09:02Z ddc:004 open_access

Learning Parities in the Mistake-Bound model Buhrman, Harry Garcia-Soriano, David Matsliah, Arie Attribute-efficient learning parities mistake-bound 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 a simple, deterministic, polynomial-time algorithm for learning $k$-parities with mistake bound $O(n^{1-frac{c}{k}})$, for any constant $c > 0$. This is the first polynomial-time algorithms that learns $omega(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 cite{rocco} for learning $k$-parities in the PAC model. We also show that the $widetilde{O}(n^{k/2})$ time algorithm from cite{rocco} that PAC-learns $k$-parities with optimal sample complexity can be extended to the mistake-bound model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harry Buhrman and David Garcia-Soriano and Arie Matsliah 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09421.5 urn:nbn:de:0030-drops-24178 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.5 eng https://creativecommons.org/licenses/by/4.0/legalcode