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

Polynomial identity testing (PIT) is the problem of checking whether a given arithmetic circuit is the zero circuit. PIT ranks as one of the most important open problems in the intersection of algebra and computational complexity. In the last few years, there has been an impressive progress on this problem ... more >>>

We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e. the problem of assigning values to the variables in a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to the fundamental problems in computational complexity ... more >>>

We study the problem of polynomial identity testing (PIT) for depth 2 arithmetic circuits over matrix algebra. We show that identity testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field F is polynomial time equivalent to identity testing of depth 2 (Pi-Sigma) arithmetic circuits over U_2(F), the algebra of ... more >>>

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

In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial factoring over finite fields. Our main result shows that given a polynomial f(x) of degree n over a finite field k, we can find in ... more >>>

In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements ... more >>>

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... more >>>

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em rank} of a minimal and simple $\Sigma\Pi\Sigma$ circuit with bounded top fanin, computing zero, can ... more >>>

We study the complexity of the isomorphism and automorphism problems for finite rings with unity. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of rings. The problem is shown to be in the complexity class $\AM \cap co\AM$ and hence is not ... more >>>