Buhrman, Harry ;
GarciaSoriano, David ;
Matsliah, Arie
Learning Parities in the MistakeBound model
Abstract
We study the problem of learning parity functions that depend on at most $k$ variables ($k$parities) attributeefficiently in the mistakebound model.
We design a simple, deterministic, polynomialtime algorithm for learning $k$parities with mistake bound $O(n^{1frac{c}{k}})$, for any constant $c > 0$. This is the first polynomialtime algorithms that learns $omega(1)$parities in the mistakebound model with mistake bound $o(n)$.
Using the standard conversion techniques from the mistakebound 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 PAClearns $k$parities with optimal sample complexity can be extended to the mistakebound model.
BibTeX  Entry
@InProceedings{buhrman_et_al:DagSemProc.09421.5,
author = {Buhrman, Harry and GarciaSoriano, David and Matsliah, Arie},
title = {{Learning Parities in the MistakeBound model}},
booktitle = {Algebraic Methods in Computational Complexity},
pages = {19},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {18624405},
year = {2010},
volume = {9421},
editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2010/2417},
URN = {urn:nbn:de:0030drops24178},
doi = {10.4230/DagSemProc.09421.5},
annote = {Keywords: Attributeefficient learning, parities, mistakebound}
}
19.01.2010
Keywords: 

Attributeefficient learning, parities, mistakebound 
Seminar: 

09421  Algebraic Methods in Computational Complexity

Issue date: 

2010 
Date of publication: 

19.01.2010 