@inproceedings{e87cbb12c48341008aa60cbd89d829b3,
title = "Learning sparse multivariate polynomials over a field with queries and counterexamples",
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 probably 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+3t)/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.",
author = "Schapire, \{Robert E.\} and Sellie, \{Linda M.\}",
year = "1993",
doi = "10.1145/168304.168307",
language = "English (US)",
isbn = "0897916115",
series = "Proceedings of the 6th annual conference on Computational learning theory, COLT 1993",
publisher = "Publ by ACM",
pages = "17--26",
booktitle = "Proceedings of the 6th annual conference on Computational learning theory, COLT 1993",
note = "Proceedings of the 6th Annual ACM Conference on Computational Learning Theory ; Conference date: 26-07-1993 Through 28-07-1993",
}