TR11-046 Authors: Shubhangi Saraf, Ilya Volkovich

Publication: 3rd April 2011 03:29

Downloads: 1577

Keywords:

We 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(k^3)}$, 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 $n^{O(k^6 \log(k) \log^2 s )}$.

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.