Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45752
Title: INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL
Authors: Bshouty, Nader H.
Cleve, Richard
Keywords: Computer Science
Issue Date: 1-May-1995
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).
URI: http://hdl.handle.net/1880/45752
Appears in Collections:Bshouty, Nader
Cleve, Richard

Files in This Item:
File Description SizeFormat 
1995-569-21.pdf205.5 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.