Factors of sparse polynomials: structural results and some algorithms

Computer Science/Discrete Mathematics Seminar II
Topic:Factors of sparse polynomials: structural results and some algorithms
Speaker:Shubhangi Saraf
Affiliation:Member, School of Mathematics
Date:Tuesday, March 26
Time/Room:10:30am - 12:30pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/0326-ShubhangiSaraf

Are factors of sparse polynomials sparse? This is a really basic question and we are still quite far from understanding it in general. In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials when the polynomial has each variable appearing only with bounded degree. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem. Using our sparsity bound, we then show how to devise efficient deterministic factoring algorithms for sparse polynomials of bounded individual degree. Along the way we will see many of the ideas used in the classical randomized blackbox factoring algorithm of Kaltofen and Trager, which we will show to derandomize in our setting. The talk is based on joint work with Vishwas Bhargav and Ilya Volkovich.