期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：study the problem of identity testing for multilinear \Spsp(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic
identity testing algorithm for such circuits. Our results also hold in the black-box setting.
The running time of our algorithm is (ns)O(k3) , where n is the number of variables,
s is the size of the circuit and k is the fan-in of the top gate.
The importance of this model arises from \cite{AgrawalVinay08}, where it was shown that derandomizing black-box polynomial identity testing for general depth-4 circuits implies a derandomization of polynomial identity testing (PIT) for general arithmetic circuits.
Prior to our work, the best PIT algorithm
for multilinear \Spsp(k) circuits~\cite{KMSV10} ran in quasi-polynomial-time, with the running time being nO(k6log(k)log2s) .
We obtain our results by showing a strong {\em structural result} for multilinear \Spsp(k) circuits that compute the zero polynomial.
We show that under some mild technical conditions, any gate of such a circuit must compute a {\em sparse} polynomial.
We then show how to combine the structure theorem with a result by Klivans and Spielman~\cite{KlivansSpielman01}, on the identity testing for sparse polynomials, to yield the full result.
