SIGTACS Lecture Series
Title: Factors of Polynomials of Low Individual Degree.
Speaker: Amit Kumar Sinhababu
Time: 11 February 2017 (Saturday), 12:00 PM
Open challenges in polynomial factorization: Polynomial factorization is one of the great success stories of computational algebra/symbolic computation. In last fifty years, researchers has developed efficient algorithms for polynomial factorization over various fields and for various representations of the input polynomial (for example, arithmetic circuit). A few questions are still open and in this lecture series we will discuss some of them. The fast two lectures would be on the following topic. A classic result due to Kaltofen states that all the factors of a polynomial computed by an arithmetic circuit of small size, can be computed by circuits of small size. One open question is whether all factors of small sized and low-depth circuits can be computed by circuits of small size and low depth. Recently Rafael Oliviera has shown that it is indeed the case, assuming that the given polynomial has bounded individual degree. He builds on a lemma due to Dvir, Shplilka and Yehudayhoff who showed the same result for linear factors. The case of unbounded individual degree is still open, even for linear factors. Paper: Factors of Polynomials of Low Individual Degree (CCC 2015, winner of the best student paper award) by Rafael Oliviera.
Back to home