Nitin Saxena, C. Seshadhri

We show that the rank of a depth-3 circuit (over any field) that is simple,

minimal and zero is at most O(k^3\log d). The previous best rank bound known was

2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005).

This almost resolves the rank question first posed by ...
more >>>

Nitin Saxena, C. Seshadhri

We study the problem of identity testing for depth-3 circuits, over the

field of reals, of top fanin k and degree d (called sps(k,d)

identities). We give a new structure theorem for such identities and improve

the known deterministic d^{k^k}-time black-box identity test (Kayal &

Saraf, FOCS 2009) to one ...
more >>>

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 polynomial time blackbox algorithm

that tests if C is identically zero.

Klivans & Spielman (STOC 2001) observed ...
more >>>