Affordable Access

Publisher Website

Efficient learning with equivalence queries of conjunctions of modulo functions

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
56
Issue
1
Identifiers
DOI: 10.1016/0020-0190(95)00126-w
Keywords
  • Learning With Queries
  • Modulo Functions
  • Analysis Of Algorithms
Disciplines
  • Computer Science

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.