Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-008 | 22nd January 1996 00:00

Learning Multivariate Polynomials from Substitution and Equivalence Queries



It has been shown in previous recent work that
multiplicity automata are predictable from multiplicity
and equivalence queries. In this paper we generalize
related notions in a matrix representation
and obtain a basis for the solution
of a number of open problems in learnability theory.
Membership queries are generalized to ``substitution''
queries for learning non-boolean functions and
provide the value of the target function for a given input.
In particular, using
substitution and equivalence queries,
we prove the learnability of the boolean XOR of terms, XOR decision trees,
decision trees with integer variables and less than conditions,
multivariate polynomials over a finite field and
rational functions over a fixed finite field. We also
provide results for the case of infinite or large fields.

ISSN 1433-8092 | Imprint