Thursday, April 25, 2019
04/25/2019 - 4:00pm
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.
The talk is based on joint work with Vishwas Bhargav and Ilya Volkovich.
04/25/2019 - 4:15pm
Abstract: A self-similar set is a compact set in Euclidean space which decomposes into similar scaled copies of itself, often disjoint from each other. For example – the middle-thirds Cantor set. The dimension theory of these sets has been (for the most part) understood for a long time. If one assumes instead that the scaled copies are related to the whole by an affine map rather than a similarities, the analysis is much harder, and results have mostly been for random (rather than individual) examples. Over the past three years the situation has changed radically and, under some very reasonable assumptions, is now completely solved in the plane. I will explain the main ingredients, which are a Ledrappier-Young type formula for the associated measures (due to Barany and Kaenmaki), and techniques from additive combinatorics developed in a joint paper with Barany and Rapaport.