Tata Institute of Fundamental Research
Sparsity bounds for factors of sparse polynomials
STCS Student Seminar
Speaker:
Varun Ramanathan
Organiser:
Varun Ramanathan
Date:
Friday, 1 Sep 2023, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
The sparsity of a polynomial is defined as the number of monomials in it. We will show that given a sparse polynomial f with bounded individual degree, the sparsity of its factors can be quasi-polynomially bounded by the sparsity of f. This result is from the paper "Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree" by Bhargava, Saraf and Volkovich. The proof is beautiful and uses techniques from convex geometry.
| Speaker: | Varun Ramanathan |
| Organiser: | Varun Ramanathan |
| Date: | Friday, 1 Sep 2023, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
The sparsity of a polynomial is defined as the number of monomials in it. We will show that given a sparse polynomial f with bounded individual degree, the sparsity of its factors can be quasi-polynomially bounded by the sparsity of f. This result is from the paper "Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree" by Bhargava, Saraf and Volkovich. The proof is beautiful and uses techniques from convex geometry.