The Taub Faculty of Computer Science Events and Talks

A central problem in algebraic complexity theory and algorithms design is the problem of Polynomial Identity Testing (PIT): given an arithmetic circuit $C$ over a field $\F$, with input variables $x_1, x_2, ... , x_n$, determine whether $C$ computes the identically zero polynomial. Numerous applications and connections to other algorithmic and number theoretic problems further emphasize the significance of PIT. Among the examples are algorithms for finding perfect matchings in graphs \cite{Lovasz79,MVV87}, primality testing \cite{AKS04}, and many more. We study the problem of PIT for multilinear $\Sigma \Pi \Sigma \Pi (k) $ circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic PIT algorithm for such circuits. Our results also hold in the black-box setting. 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. We obtain our results by showing a strong structural result for multilinear $\Sigma \Pi \Sigma \Pi (k) $ circuits that compute the zero polynomial.