|
Title:
|
Learning read-constant polynomials of constant degree modulo composites
|
|
Author:
|
Chattopadhyay, Arkadev; Gavaldà Mestre, Ricard; Arnsfelt Hansen, Kristoffer; Thérien, Denis
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge |
|
Abstract:
|
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. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
-Computational complexity
-Algebra, Boolean
-Polynomials over finite rings
-Exact learning
-Membership queries
-Modular gates
-Complexitat computacional
-Àlgebra booleana |
|
Rights:
|
|
|
Document type:
|
Article - Submitted version
Article |
|
Share:
|
|
