Learning Read-constant Polynomials of Constant Degree modulo Composites

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

  • Arkadev Chattopadhyay, University of Toronto, Canada
  • Richard Gavaldá, Universitat Polit`ecnica de Catalunya
  • ,
  • Kristoffer Arnsfelt Hansen
  • Denis Thérien, McGill University
  • Department of Computer Science
Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class \textACC0ACC0. 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
Book seriesLecture Notes in Computer Science
Volume6651
Pages (from-to)29-42
Number of pages14
ISSN0302-9743
DOIs
Publication statusPublished - 2011
Event6th International Computer Science Symposium in Russia - Skt. Petersborg, Russian Federation
Duration: 14 Jun 201118 Jun 2011

Conference

Conference6th International Computer Science Symposium in Russia
CountryRussian Federation
CitySkt. Petersborg
Period14/06/201118/06/2011

Bibliographical note

Title of the vol.: Computer Science – Theory and Applications. Proceedings / Alexander Kulikov and Nikolay Vereshchagin (eds.)
ISBN: 978-3-642-20711-2

See relations at Aarhus University Citationformats

ID: 41569204