Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 2/2014

01-08-2014

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

Authors: Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien

Published in: Theory of Computing Systems | Issue 2/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article The Complexity of Solving Reachability Games Using Value and Strategy Iteration
next article Two-Way Automata Versus Logarithmic Space

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
In an equivalence query, the learning algorithm emits some representation of a Boolean function and receives as answer either a Boolean assignment where it differs from the target function, or “yes” if no such assignment exists.
 
2
Alternatively one could fix the same ordering, say 1,…,n for all monomials. However we find it natural to identify monomials that are identical up to a permutation of the variables.
 
3
A DNF formula is read-k if every variable appears at most k times; a DNF formula is satisfy-j if no assignment satisfies more than j terms simultaneously.
 
Literature
1.
Aizenstein, H., Blum, A., Khardon, R., Kushilevitz, E., Pitt, L., Roth, D.: On learning read-k-satisfy-j dnf. SIAM J. Comput. 27(6), 1515–1530 (1998) CrossRefMATHMathSciNet
2.
Aizenstein, H., Hegedüs, T., Hellerstein, L., Pitt, L.: Complexity theoretic hardness results for query learning. Comput. Complex. 7(1), 19–53 (1998) CrossRefMATH
3.
4.
Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38(1), 150–164 (1989) CrossRefMATHMathSciNet
5.
Barrington, D.A.M., Beigel, R., Rudich, S.: Representing boolean functions as polynomials modulo composite numbers. Comput. Complex. 4, 367–382 (1994) CrossRefMATHMathSciNet
6.
Barrington, D.A.M., Straubing, H.: Superlinear lower bounds for bounded-width branching programs. J. Comput. Syst. Sci. 50(3), 374–381 (1995) CrossRefMATHMathSciNet
7.
Barrington, D.A.M., Straubing, H., Thérien, D.: Non-uniform automata over groups. Inf. Comput. 89(2), 109–132 (1990) CrossRefMATH
8.
Barrington, D.A.M., Thérien, D.: Finite monoids and the finite structure of NC1. J. ACM 35(4), 941–952 (1988) CrossRef
9.
Beimel, A., Bergadano, F., Bshouty, N., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. J. ACM 47, 506–530 (2000) CrossRefMATHMathSciNet
10.
Bourgain, J.: Estimation of certain exponential sums arising in complexity theory. C. R. Math. Acad. Sci. 340(9), 627–631 (2005) CrossRefMATHMathSciNet
11.
Braverman, M., Rao, A., Raz, R., Yehudayoff, A.: Pseudorandom generators for regular branching programs. In: 51th Annual IEEE Symposium on Foundations of Computer Science, pp. 40–47. IEEE Comput. Soc., Los Alamitos (2010)
12.
Brody, J., Verbin, E.: The coin problem, and pseudorandomness for branching programs. In: 51th Annual IEEE Symposium on Foundations of Computer Science, pp. 30–39. IEEE Comput. Soc., Los Alamitos (2010)
13.
14.
Chattopadhyay, A.: Multilinear polynomials modulo composites. In: Bulletin of the European Association on Theoretical Computer Science, Computational Complexity Column, vol. 100 (2010)
15.
Efremenko, K.: 3-query locally decodable codes of subexponential length. In: 41st Annual Symposium on Theory of Computing, pp. 39–44. ACM, New York (2009) CrossRef
16.
Gavaldà, R., Thérien, D.: An algebraic perspective on boolean function learning. In: Algorithmic Learning Theory, 20th International Conference, ALT 2009. LNCS, pp. 201–215. Springer, Berlin (2009)
17.
Gopalan, P.: Constructing Ramsey graphs from boolean function representations. In: 21st Annual IEEE Conference on Computational Complexity, pp. 115–128. IEEE Comput. Soc., Los Alamitos (2006)
18.
Grolmusz, V.: On the weak mod m representation of boolean functions. Chic. J. Theor. Comput. Sci. (1995)
19.
Helmbold, D.P., Sloan, R.H., Warmuth, M.K.: Learning nested differences of intersection-closed concept classes. Mach. Learn. 5, 165–196 (1990)
20.
Koucký, M., Nimbhorkar, P., Pudlák, P.: Pseudorandom generators for group products. In: 43rd Annual ACM Symposium on Theory of Computing, pp. 263–272. ACM, New York (2011)
21.
Péladeau, P., Thérien, D.: Sur les langages reconnus par des groupes nilpotents. C. R. Math. Acad. Sci. Paris 306(2), 93–95 (1988) MATH
22.
Péladeau, P., Thérien, D.: On the languages recognized by nilpotent groups (a translation of “Sur les langages reconnus par des groupes nilpotents” [21]). Electron. Colloq. Comput. Complex. 8(40) (2001)
23.
24.
Razborov, A.A.: Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41(3), 333–338 (1987) CrossRefMATHMathSciNet
25.
Schapire, R.E., Sellie, L.: Learning sparse multivariate polynomials over a field with queries and counterexamples. J. Comput. Syst. Sci. 52(2), 201–213 (1996) CrossRefMATHMathSciNet
26.
Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: 19th Annual ACM Symposium on Theory of Computing, pp. 77–82. ACM, New York (1987)
27.
Metadata
Title
Learning Read-Constant Polynomials of Constant Degree Modulo Composites
Authors
Arkadev Chattopadhyay
Ricard Gavaldà
Kristoffer Arnsfelt Hansen
Denis Thérien
Publication date
01-08-2014
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 2/2014
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-013-9488-6

Other articles of this Issue 2/2014

Theory of Computing Systems 2/2014 Go to the issue

OriginalPaper

Join-Reachability Problems in Directed Graphs

OriginalPaper

Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization

OriginalPaper

Two-Way Automata Versus Logarithmic Space

OriginalPaper

Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error

EditorialNotes

Editorial

OriginalPaper

The Equivalence of Sampling and Searching

Premium Partner

    Image Credits