Chennai Mathematical Institute

Seminars




CS Faculty Talks
Date: Monday, 7 October 2024
Time: 02:00 - 02:50 PM
Venue: Seminar Hall
Derandomizing Multivariate Polynomial Factoring for Low Degree Factors

Amit K Sinhababu
Chennai Mathematical Institute.
07-10-2024


Abstract

Kaltofen [STOC 1986] gave a randomized algorithm to factor multi- variate polynomials given by algebraic circuits. We derandomize the algorithm in some special cases, when the input polynomial is sparse or product of linear/constant-degree polynomials, and when we want only linear/constant-degree factors.