INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL

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).