Computer Science – Computational Complexity
Scientific paper
2010-11-14
Computer Science
Computational Complexity
14 pages, 1 figure, preliminary version
Scientific paper
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 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 sps(k,d,n) circuit to k variables, but preserves the identity structure.
Saxena Nitin
Seshadhri C.
No associations
LandOfFree
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-456330