INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL
Date
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