Lecture Announcement
Date and Time: Wednesday, 6th April 2022, 9pm (Online)
Multivariate polynomial factorization: An algebraic complexity perspective
Amit Kumar Sinhababu
Aalen University, Germany.
06-04-22

---

Abstract

Multivariate polynomial factorization is a classic problem that has found interesting applications in algebraic complexity theory. It is a basic theorem that the polynomial ring is a unique factorization domain, but the standard proof for this does not give an algorithm for factoring polynomials. Kronecker gave the first such algorithm, which takes exponential time. A series of works in the 1970s and 1980s built efficient algorithms for the problem using classical tools like Hensel lifting or Newton iteration.

To discuss the complexity of the problem, one has to fix a representation for the input polynomial and output factors. A standard way of representing polynomials is via arithmetic circuits. In a classic result, Kaltofen showed that the factors of small arithmetic circuits of low degree can be computed by small arithmetic circuits.

In this talk, I would discuss our attempts to extend Kaltofen's result to various other models like arithmetic formulas, branching programs, high degree circuits, etc. (based on joint works with Pranjal Dutta, Nitin Saxena, and Thomas Thierauf)