Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-011 | 22nd January 2010 09:49

Read-Once Polynomial Identity Testing


Authors: Amir Shpilka, Ilya Volkovich
Publication: 22nd January 2010 09:49
Downloads: 1497


An \emph{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 such that every input variable
labels at most one leaf. A \emph{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)$. In this paper we
study the problems of giving deterministic identity testing for
models related to preprocessed ROFs. Our main result gives PIT
algorithms for the sum of $k$ preprocessed ROFs, of individual
degrees at most $d$ (i.e. each $T_i(x_i)$ is of degree at most
$d$), that run in time $(nd)^{O(k)}$ in the non black-box
model and in time $(nd)^{O(k + \log n)}$ in the black-box
model. We also obtain better algorithms where the formulas have a
small depth that lead to an improvement on the best PIT algorithm
for multilinear $\Sigma\Pi\Sigma(k)$ circuits.

Our main technique is to prove a {\em hardness of representation}
result. Namely, a theorem showing a relatively mild lower bound on
the sum of $k$ PROFs. We then use this lower bound in order to
design our PIT algorithm.

ISSN 1433-8092 | Imprint