Equivalence Test for Read-Once Arithmetic Formulas

We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two n-variate polynomials f , g ∈ F[x] are equivalent, denoted as f ∼ g, if there is an A ∈ GL(n, F) such that f = g(Ax). The orbit of f is the set of all polynomials equivalent to f . We investigate the complexity of the following two natural problems on ROFs:

• Equivalence test for ROFs: Given black-box access to f , check if it is in the orbit of an ROF.

If yes, output an ROF C and an A ∈ GL(n, F) such that f = C(Ax).

• Polynomial equivalence for orbits of ROFs: Given black-box access to f and g in the orbits of two unknown ROFs, check if f ∼ g. If yes, output an A ∈ GL(n, F) such that f = g(Ax).