INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL
Date
1995-05-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A formula is read-once if each variable appears at most once in it. An
artithmetic read-once formula is one in which the operations are
addition, subtraction, multiplication, and division (and constants are
allowed). We present a randomized (Las Vegas) parallel algorithm for the
exact interpolation of arithmetic read-once formulas over sufficiently
large fields. More specifically, for n-variable read-once formulas,
and fields of size at least $3(n sup 2 + 3n - 2)$, our algorithm
runs in $O(log sup 2 n)$ parallel steps using $O(n sup 4)$
processors (where the field operations are charged unit cost). This
complements other results which imply that other classes of read-once
formulas cannot be interpolated-or even learned with membership
and equivalence queries-in poly-logarithmic-time with polynomially many
processors (even though they can be learned sequentially in
polynomial-time). These classes include boolean read-once formulas and
arithmetic read-once formulas over fields of size o(n/log n)
(for n variable read-once formulas).
Description
Keywords
Computer Science