Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.
It is a major open problem to design a deterministic polynomial time blackbox algorithm
that tests if C is identically zero.
Klivans & Spielman (STOC 2001) observed that the problem
is open even when k is a constant.
This case has been subjected to a serious study over the past few years, starting
from the work of Dvir & Shpilka (STOC 2005).
We give the first polynomial time blackbox algorithm for this problem. Our algorithm
runs in time poly(nd^k), regardless of the base field. The *only* field
for which polynomial time algorithms were previously known
is F=Q (Kayal & Saraf, FOCS 2009, and Saxena & Seshadhri, FOCS 2010).
This is the first blackbox algorithm for depth-3 circuits that does not use
the rank based approaches of Karnin & Shpilka (CCC 2009).
We prove an important tool for the study of depth-3 identities. We design
a blackbox polynomial time transformation that reduces the number of variables
in a sps(k,d,n) circuit to k variables, but preserves the identity structure.