2025/06/24 by C. S. Bhargav, Bhargav, C. S., Prateek Dwivedi +3
Computer Science · Engineering · Mathematics · #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Polynomial and algebraic computation #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2506.19604
openalex publication_date 2025/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 VP (circuits of polynomial size and degree), its closure VP, the class VNP (verifier circuits of polynomial size and degree), VBP (polynomial-size branching programs), VF (polynomial-size formulas), and VPnb (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.