TR10-011 Authors: Amir Shpilka, Ilya Volkovich

Publication: 22nd January 2010 09:49

Downloads: 3300

Keywords:

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.