Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Learning read-constant polynomials of constant degree modulo composites

Autor
Chattopadhyay, A.; Gavaldà, R.; Arnsfelt Hansen, K.; Thérien, D.
Tipus d'activitat
Article en revista
Revista
Theory of computing systems
Data de publicació
2013-07-01
Volum
55
Número
2
Pàgina inicial
404
Pàgina final
420
DOI
https://doi.org/10.1007/s00224-013-9488-6 Obrir en finestra nova
Projecte finançador
MINERIA EN DATOS BIOLOGICOS Y SOCIALES: ALGORITMOS, TEORIA E IMPLEMENTACION
SGR2009-1428
Repositori
http://hdl.handle.net/2117/28159 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007%2Fs00224-013-9488-6 Obrir en finestra nova
Resum
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 arb...
Citació
Chattopadhyay, A. [et al.]. Learning read-constant polynomials of constant degree modulo composites. "Theory of computing systems", Agost 2014, vol. 55, núm. 2, p. 404-420.
Paraules clau
Exact learning, Membership queries, Modular gates, Polynomials over finite rings
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants

  • Chattopadhyay, Arkadev  (autor)
  • Gavaldà Mestre, Ricard  (autor)
  • Arnsfelt Hansen, Kristoffer  (autor)
  • Thérien, Denis  (autor)

Arxius