Some Closure Results for Polynomial Factorization and Applications

Understand

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.