Revised: July 18, 2014

Published: December 26, 2014

**Keywords:**read-once formulas, identity testing, reconstruction, arithmetic circuits, bounded-depth circuits

**Categories:**complexity theory, algorithms, formulas, read-once formulas, polynomial identity testing, arithmetic circuits, bounded-depth circuits

**ACM Classification:**F.1.3, F.2.2

**AMS Classification:**68Q15, 68Q25

**Abstract:**
[Plain Text Version]

An *arithmetic read-once formula* (ROF for short) is a
formula (a circuit whose underlying graph is a tree) in which the
operations are $\{+,\times\}$ 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
$x_i$ with a univariate polynomial $T_i(x_i)$.
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)^{\BigO(\log n)}$ 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(\bar{x})$, decide whether there is a PROF
computing $P(\bar{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. In this work we show
that most previous PIT algorithms
be strengthened to yield algorithms for the
ROT
problem. In particular we give ROT algorithms for the following
circuit classes:
depth-$2$
circuits (circuits computing sparse
polynomials),
depth-$3$
circuits with bounded top fan-in, and sum of $k$
ROFs. The running time of the ROT algorithm is essentially the
same
as the running time of the
corresponding PIT algorithm for the class.

The main tool in most of our results is a new connection between PIT and reconstruction of ROFs. Namely, we show that in any model that satisfies some “nice” closure properties (for example, a partial derivative of a polynomial computed by a circuit in the model, can also be computed by a circuit in the model) and that has an efficient deterministic polynomial identity testing algorithm, we can also answer the read-once testing problem.

An extended abstract of this paper appeared in the Proceedings of the 40th Annual Symposium on Theory of Computing (STOC 2008), pages 507-516.