期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 − k c ) , for any constant 0"> c 0 . These are the first polynomial-time algorithms that learn (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 algorithms can also be used for learning k -parities in the PAC model. In particular, this implies a slight improvement over the results of Klivans and Servedio for learning k -parities in the PAC model. We also show that the O ( n k 2 ) time algorithm from Klivans and Servedio's paper that PAC-learns k -parities with optimal sample complexity can be extended to the mistake-bound model.
0 . These are the first polynomial-time algorithms that learn 
