  In a sequence of seminal results in the 80's, Kaltofen showed that the
complexity class VP 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 VNP, 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., 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 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 low degree.
  As direct applications of our techniques, we also show that the complexity
class VNP is closed under taking factors, thereby confirming a conjecture of
B\"urgisser and get an alternate proof of the fact (first shown by Dutta et
al.) that if a polynomial $Q$ of degree at most $d$ divides a polynomial $P$
computable by a formula of size $s$, then $Q$ has a formula of size at most
poly$(s, d^{\log d}, deg(P))$.
