Theory of Computing
-------------------
Title : On Reconstruction and Testing of Read-Once Formulas
Authors : Amir Shpilka and Ilya Volkovich
Volume : 10
Number : 18
Pages : 465-514
URL : http://www.theoryofcomputing.org/articles/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
$\{+,\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)^{O(\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.