Polynomial factorisation is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their computational hardness. This raises a natural question: Are these complexity classes closed under factorisation?

In this survey, we revisit pivotal techniques in polynomial factorisation: Hensel lifting, Newton iteration, and Lagrange inversion. These techniques have played an essential role in resolving key factoring questions in algebraic complexity for more than half a century. We examine and organise the known results through the lens of these techniques, discussing their underlying mathematical equivalence while reflecting on how their applications vary depending on the problem context.

We focus on prominent algebraic complexity classes, including $\text{VP}$ (circuits of polynomial size and degree), its closure $\overline{\text{VP}}$, the class $\text{VNP}$ (verifier circuits of polynomial size and degree), $\text{VBP}$ (polynomial-size branching programs), $\text{VF}$ (polynomial-size formulas), and $\text{VP}_{\text{nb}}$ (circuits of polynomial size and exponential degree). We also discuss bounded-depth circuits and sparse polynomials. Along the way, we highlight several unresolved open problems.

The updated version includes an exposition of the recent breakthrough on formula and bounded-depth factoring.

Polynomial factorization is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their perceived `hardness'. This raises a natural question: Do these classes afford efficient factorization?

In this survey, we revisit two pivotal techniques in polynomial factorization: Hensel lifting and Newton iteration.
Though they are variants of the same theme, their distinct applications across the literature warrant separate treatment.
These techniques have played an important role in resolving key factoring questions in algebraic complexity theory.
We examine and organise the known results through the lens of these techniques to highlight their impact. We also discuss their equivalence while reflecting on how their use varies with the context of the problem.

We focus on four prominent complexity classes: circuits of polynomial size ($\text{VP}_{\text{nb}}$), circuits with both polynomial size and degree (VP and its border $\overline{\text{VP}}$), verifier circuits of polynomial size and degree (VNP), and polynomial-size algebraic branching programs (VBP). We also examine more restricted models, such as formulas and bounded-depth circuits. Along the way, we list several open problems that remain unresolved.