On learning arithmetic read-once formulas with exponentiation (extended abstract)

摘要

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.

Interpolating AROF without exponentiation is studied in [Bshouty, Hancock and Hellerstein, STOC 92]. To add the exponentiation operation to the basis we develop a new technique.