LEARNING ARITHMETIC READ-ONCE FORMULAS
Date
1992-08-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A formula is read-once if
each variable appears at most once in it. An arithmetic read-once
formula is one in which the operators are addition, subtraction,
multiplication, and division. We present polynomial time algorithms
for exact learning (i.e. interpolation) of arithmetic read-once
formulas computing functions over a field. We present an algorithm
that uses randomized membership queries (i.e. substitutions) to
identify such formulas over large finite fields and infinite fields.
We also present a deterministic algorithm that uses equivalence
queries as well as membership queries to identify arithmetic read-once
formulas over small finite fields. We then non-constructively show
the existence of deterministic membership query (interpolation)
algorithms for arbitrary formulas over fields of characteristic 0 and
for division-free formulas over large or infinite fields. For our
algorithms we assume we are able to efficiently perform arithmetic
operations on field elements and compute square roots in the field.
It is shown that the ability to compute square roots is necessary, in
the sense that the problem of computing n-1 square roots in a
field can be reduced to the problem of identifying an arithmetic
formula over n variables in that field. Our equivalence queries
are of a slightly non-standard form, in which counterexamples are
required not to be inputs on which the formula evaluates to 0/0. This
assumption is shown to be necessary for fields of size o(n/logn),
for which we prove there exists no polynomial time
identification algorithm that uses just membership and standard
equivalence queries.
Description
Keywords
Computer Science