Factors of sparse polynomials: structural results and some algorithms

Abstract: Are factors of sparse polynomials sparse? This is basic question, and we are still quite far from understanding it in general. In this talk, I will show 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. The talk is based on joint work with Vishwas Bhargav and Ilya Volkovich.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456