ECCC-Report TR10-011https://eccc.weizmann.ac.il/report/2010/011Comments and Revisions published for TR10-011en-usFri, 22 Jan 2010 09:49:27 +0200
Paper TR10-011
| Read-Once Polynomial Identity Testing |
Amir Shpilka,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2010/011An \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.
Fri, 22 Jan 2010 09:49:27 +0200https://eccc.weizmann.ac.il/report/2010/011