__
TR10-167 | 5th November 2010 16:44
__

#### Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

**Abstract:**
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.