AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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. This partially solves the "factor conjecture" proposed by Peter Bürgisser.

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

Christian Ikenmeyer

--email hidden

passcode not visible

logged in users only