BARC talk by Varun Ramanathan

Thursday, October 31, 2024, Varun Ramanathan, PhD student at TIFR Mumbai, India, will give a talk on "Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits".

Abstract:
Multivariate polynomial factorization is a natural algebraic problem with a lot of applications. von zur Gathen, Kaltofen, Trager et al gave us randomized algorithms for factoring black-box polynomials as well as polynomials given as explicit arithmetic circuits. Derandomization of these algorithms is connected to the derandomization of polynomial identity testing (by a result of Kopparty, Saraf and Shpilka) but the connection is not "fine-grained''; for instance, recent breakthroughs in deterministic PIT for constant-depth circuits have not immediately led to improvements in deterministic factorization of constant-depth circuits.

In this talk, we will see an algorithm that makes some modest progress towards this problem. In particular, we will see a deterministic subexponential time algorithm that takes as input a multivariate polynomial f computed by a constant-depth circuit over rational numbers, and outputs a list L of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of f computable by constant-depth circuits. This list L might also include circuits that are spurious: they either do not correspond to factors of f or are not even well-defined, e.g. the input to a division gate is a sub-circuit that computes the identically zero polynomial.

The key technical ingredient of our algorithm is a notion of the pseudo-resultant of f and a factor g, which serves as a proxy for the resultant of g and f/g, with the advantage that the circuit complexity of the pseudo-resultant is comparable to that of the circuit complexity of f and g. This notion, which might be of independent interest, together with the recent results of Limaye, Srinivasan and Tavenas, helps us derandomize one key step of multivariate polynomial factorization algorithms - that of deterministically finding a good starting point for Newton Iteration for the case when the input polynomial as well as the irreducible factor of interest have small constant-depth circuits.

This is joint work with Ramprasad Saptharishi, Mrinal Kumar and Ben Lee Volk. (https://eccc.weizmann.ac.il/report/2024/043/)

Bio:
Varun Ramanathan is a PhD student at TIFR Mumbai, advised by Prof. Ramprasad Saptharishi and Prof. Mrinal Kumar. He likes complexity theory, coding theory, pseudorandomness and everything algebraic. He also likes running, climbing, and playing percussive instruments.

Host:
Srikanth Srinivasan