Read-once polynomial identity testing
Amir Shpilka, Ilya Volkovich · Computational Complexity · 2008
An arithmetic read-once formula (ROF for short) is a formula (a circuit whose underlying graph is a tree) in which the operations are $${\left\{+, \times \right\}}$$ and such that every 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 ). In this paper, we study the problems of designing deterministic identity testing algorithms 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)^{\mathcal{O}(k)}}$$ in the white-box setting and in time $${(nd)^{\mathcal{O}(k + \log n)}}$$ in the black-box setting. We also obtain better algorithms when the formulas have a small depth that lead to an improvement in the best PIT algorithm for multilinear depth-3 $${\Sigma\Pi\Sigma(k)}$$ circuits. Our main technique is to prove a 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.