On learning arithmetic read-once formulas with exponentiation (extended abstract)
Daoud Bshouty, Nader H. Bshouty · 1994
A formula is a read-once formula if each variable appears at most once in it. An arithmetic read-once formula (AROF) with exponentiation is one in which the operations are addition, subtraction, multiplication, division and exponentiation to an arbitrary integer. We present a polynomial time algorithm for interpolating AROF with exponentiation using randomized substitutions. We then nonconstructively show the existence of a nonuniform deterministic algorithm.