Let C be a depth-3 arithmetic circuit of size s , computing a polynomial f F [ x 1 x n ] (where F = Q or C ) with fan-in of product gates bounded by d . We give a deterministic time 2 d poly ( n s ) polynomial identity testing algorithm to check whether f 0 or not.

In the case of finite fields, for d"> Char ( F ) d we obtain a deterministic algorithm of running time 2 d poly ( n s ) , whereas for Char ( F ) d , we obtain a deterministic algorithm of running time 2 ( +2) d log d poly ( n s ) where 5 .