Learning sparse multivariate polynomials over a field with queries and counterexamples

Robert E. Schapire, Linda M. Sellie

Research output: Contribution to journalArticle

26 Scopus citations

Abstract

We consider the problem of learning a polynomial over an arbitrary field F defined on a set of boolean variables. We present the first provably effective algorithm for exactly identifying such polynomials using membership and equivalence queries. Our algorithm runs in time polynomial in n, the number of variables, and t, the number of nonzero terms appearing in the polynomial. The algorithm makes at most nt + 2 equivalence queries, and at most (nt + 1)(t2 + 3f)/2 membership queries. Our algorithm is equally effective for learning a generalized type of polynomial defined on certain kinds of semilattices. We also present an extension of our algorithm for learning multilinear polynomials when the domain of each variable is the entire field F.

Original languageEnglish (US)
Pages (from-to)201-213
Number of pages13
JournalJournal of Computer and System Sciences
Volume52
Issue number2
DOIs
StatePublished - Apr 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Learning sparse multivariate polynomials over a field with queries and counterexamples'. Together they form a unique fingerprint.

  • Cite this