Factors of succinctly computable polynomials

Title of the Talk: Factors of succinctly computable polynomials
Speakers: Ramprasad Saptharishi
Host Faculty: Dr.N R Aravind
Date: Sep 3, 2025
Time: 11:00 am to 12:00
Venue: CSE-LH2 Building

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).

Bio:
Ramprasad Saptharishi is a faculty member at the School of Technology and Computer Science at the Tata Institute of Fundamental Research. He received his PhD from Chennai Mathematical Institute and subsequently completed his postdoc in Microsoft Research India and Tel Aviv University. His academic interests are broadly in the area of algebraic computation and coding theory.