Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Are factors of Sparse polynomials sparse?

Vishwas Bhargava, Rutgers

Location:  Hill 705
Date & time: Monday, 25 February 2019 at 2:00PM - 3:00PM

 

Abstract:  The main question we will discuss is, how number of terms of a polynomial(a.k.a Sparsity) relates to number of terms of its factors. This is a fundamental problem which lies at the intersection of Algebra and Combinatorics and attracted attention from several authors, including Erdös, Freud, Rényi, Schinzel and Verdenius.  We show a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular, we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s^{O({d^2log{n}})}. This is the first nontrivial bound on factor sparsity for d >2. 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. 

Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.

Joint work with Shubhangi Saraf and Ilya Volkovich.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.