An Almost Optimal Rank Bound for Depth-3 Identities

We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most k^3log 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 (as we also provide a simple and minimal identity of rank Omega(klog d)). Our rank bound significantly improves (dependence on k exponentially reduced) the best known deterministic black-box identity tests for depth-3 circuits by Karnin and Shpilka (CCC 2008). Our techniques also shed light on the factorization pattern of nonzero depth-3 circuits, most strikingly: the rank of linear factors of a simple, minimal and nonzero depth-3 circuit (over any field) is at most k^3log d. The novel feature of this work is a new notion of maps between sets of linear forms, called ideal matchings, used to study depth-3 circuits. We prove interesting structural results about depth-3 identities using these techniques. We believe that these can lead to the goal of a deterministic polynomial time identity test for these circuits.

Schemes for Deterministic Polynomial Factoring

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 in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.