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).
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca