Efficient Learning with Equivalence Queries of Conjunctions of Modulo Functions

Alberto Bertoni, Nicolò Cesa-Bianchi, Guido FiorinoInf. Process. Lett 1995 · DOI · OpenReview

Abstract

A modulo m function takes value 0 when the weighted sum of the input variables is congruent to 0 mod m and takes value 1 otherwise. In this work we show a polynomial time algorithm for learning with equivalence queries the class of conjunctions of modulo p functions on n variables, for any fixed prime p. The result is also extended to learning with bounded adversarial noise.
BibTeX
@article{bertoni1995efficient,
  author = {Alberto Bertoni and Nicolò Cesa-Bianchi and Guido Fiorino},
  title = {{Efficient Learning with Equivalence Queries of Conjunctions of Modulo Functions}},
  journal = {Inf. Process. Lett.},
  year = {1995},
  doi = {10.1016/0020-0190(95)00126-w},
}

Loading related content...

Figure