Chennai Mathematical Institute

Seminars




2:00 pm, Lecture Hall 6
Discovering the roots: Uniform closure results for algebraic classes under factoring

Pranjal Dutta
Chennai Mathematical Institute.
23-10-17


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.

This is based on joint work with Nitin Saxena (IIT Kanpur) and Amit Sinhababu (IIT Kanpur).