Blackbox identity testing for bounded top fanin depth-3 circuits

Abstract

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called ΣΠΣ(k,d,n) circuits) over base field FF. 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(n)dk, regardless of the base field. The only field for which polynomial time algorithms were previously known is FF = QQ (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 2008). 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 ΣΠΣ(k,d,n) circuit to k variables, but preserves the identity structure.