Learning Read-Constant Polynomials of Constant Degree Modulo Composites

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Arkadev Chattopadhyay, Tata Institute of Fundamental Research, India
  • Ricard Gavaldà, Universitat Politècnica de Catalunya, Denmark
  • Kristoffer Arnsfelt Hansen
  • Denis Thérien, McGill University, Canada

Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC0. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.

Original languageEnglish
JournalTheory of Computing Systems
Volume55
Issue2
Pages (from-to)404-420
Number of pages17
ISSN1432-4350
DOIs
Publication statusPublished - 2014

    Research areas

  • Exact learning, Membership queries, Modular gates, Polynomials over finite rings

See relations at Aarhus University Citationformats

ID: 78981677