31 citations · 82 across the 22 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.CC2010
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter
Nitin Saxena, C. Seshadhri
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 polynomia…
cs.CC2010★ 1 cited
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits
Nitin Saxena, C. Seshadhri
We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem…