cb Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2014.v010a018

Abstract: An arithmetic read-once formula (ROF for short) is a formula (a circuit whose underlying graph is a tree) in which the operations are {+,×} and each input variable labels at most one leaf. A preprocessed ROF (PROF for short) is a ROF in which we are allowed to replace each variable xi with a univariate polynomial Ti(xi). We obtain a deterministic non-adaptive reconstruction algorithm for PROFs, that is, an algorithm that, given black-box access to a PROF, constructs a PROF computing the same polynomial. The running time of the algorithm is (nd)O(logn) for PROFs of individual degrees at most d. To the best of our knowledge our results give the first subexponential-time deterministic reconstruction algorithms for ROFs. Another question that we study is the following generalization of the polynomial identity testing (PIT) problem. Given an arithmetic circuit computing a polynomial P(x̄), decide whether there is a PROF computing P(x̄), and find one if one exists. We call this question the read-once testing problem (ROT for short). Previous (randomized) algorithms for reconstruction of ROFs imply that there exists a randomized algorithm for the ROT problem