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:DSP:2010:2417,
author = {Harry Buhrman and David GarciaSoriano and Arie Matsliah},
title = {Learning Parities in the MistakeBound model},
booktitle = {Algebraic Methods in Computational Complexity},
year = {2010},
editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
number = {09421},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2417},
annote = {Keywords: Attributeefficient learning, parities, mistakebound}
}
Keywords: 

Attributeefficient learning, parities, mistakebound 
Seminar: 

09421  Algebraic Methods in Computational Complexity

Issue date: 

2010 
Date of publication: 

19.01.2010 