Title | : | Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring |

Speaker | : | Pranjal Dutta (CMI, Chennai) |

Details | : | Wed, Jan 17, 2018 3:00 PM, @ Turing Hall |

Abstract | : | Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. I will talk about generalizing it to a matrix recurrence that approximates all the roots "simultaneously". I will also discuss an interesting property of multivariate polynomial factorization which shows that under a random linear transformation τ , f(τx) completely factors via power series roots. Combining these, I will establish that for an algebraic circuit f(x_1, . . . , x_n) of size s, each factor has size at most a polynomial in: s and the degree of the square-free part of f.For the remaining time, I will talk about different model of interest when the given polynomial f is of degree poly(n) and can be computed by a formula (resp. Algebraic Branching Program) size n^{O(log n)} . I will show how to find a similar size formula (resp. ABP) factor in randomized poly(n^{log n})-time. The talk will be self-contained. This is based on joint work with Nitin Saxena (IIT Kanpur) and Amit Sinhababu (IIT Kanpur). |