Computer Science Seminar
Date: Monday, 29 September 2025
Time: 11.30 a.m.
Venue: Lecture Hall 2, CMI
Factors of succinctly computable polynomials
Ramprasad Saptharishi
TIFR, Mumbai.
29-09-25

---

Abstract

The field of algebraic complexity deals with study of multivariate polynomials, and how easy (or hard) it is to compute them using "algebraic circuits / formulas". In this talk, we will focus on the following question: Given a polynomial that is computed by a small algebraic circuit, can we also compute its factors using small circuits?

One of the miracles in the field is a result of Kaltofen (from the 80s) that gave a positive answer to this question. However, it was not known if the same result holds if we replace the word 'circuits' with 'formulas' or 'constant-depth circuits'. In this talk, we shall see that the above holds for not just formulas or constant-depth circuits, but for any "reasonable" model of computation.

The key technical insight can in fact be traced to the classical (18th century!) Lagrange Inversion Formula, which is then used to give 'explicit' descriptions of implicitly-defined power series.

This is joint work with Somnath Bhattacharjee (U Toronto), Mrinal Kumar (TIFR), Shanthanu Rai (TIFR), Varun Ramanathan (TIFR), and Shubhangi Saraf (U Toronto).