In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class V P is closed under taking factors. A natural question in this context is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, bounded depth arithmetic circuits or the class VN P , are closed under taking factors.

In this paper, we show that all factors of degree at most log a n of polynomials with poly ( n ) size depth k circuits have poly ( n ) size circuits of depth at most O ( k + a ) . This partially answers a question of Shpilka-Yehudayoff and has applications to hardness-randomness tradeoffs for bounded depth arithmetic circuits.

More precisely, this shows that a superpolynomial lower bound for bounded depth arithmetic circuits, for a family of explicit polynomials of degree poly ( log n ) implies deterministic sub-exponential time algorithms for polynomial identity testing (PIT) for bounded depth arithmetic circuits. This is incomparable to a beautiful result of Dvir et al. [DSY09], where they showed that super-polynomial lower bounds for constant depth arithmetic circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for bounded depth circuits of \emph{bounded individual degree}. Thus, we remove the ``bounded individual degree" condition in [DSY09] at the cost of strengthening the hardness assumption to hold for polynomials of \emph{low} degree.

As direct applications of our techniques, we also obtain simple proofs of the following results. \begin{itemize} \item The complexity class VN P is closed under taking factors. This confirms a conjecture of B{\"u}rgisser , and improves upon a recent result of Dutta, Saxena and Sinhababu who showed a quasipolynomial upper bound on the number of auxiliary variables and the complexity of the verifier circuit of factors of polynomials in VN P .

\item A factor of degree at most d of a polynomial P which can be computed by an arithmetic formula (resp. algebraic branching program) of size s has a formula (resp. algebraic branching program) of size at most poly ( s d log d d e g ( P )) . This result was first shown by Dutta et al., and we obtain a slightly different proof as an easy consequence of our techniques. \end{itemize} Our proofs rely on a combination of the \emph{lifting} based ideas developed in polynomial factoring literature and the depth reduction results for arithmetic circuits, and hold over fields of characteristic zero or sufficiently large.