Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-167 | 5th November 2010 16:44

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


Authors: Nitin Saxena, C. Seshadhri
Publication: 6th November 2010 00:23
Downloads: 2589


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.

ISSN 1433-8092 | Imprint