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 Dvir and Shpilka ... more >>>

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 >>>