Fall 2014

On the Complexity of Solving Bivariate Systems

Thursday, October 16th, 2014 10:30 am10:55 am

Add to Calendar


Calvin Lab Auditorium

We present an algorithm for solving bivariate polynomial systems with coefficients in $\mathbb{Q}$ with essentially optimal bit complexity. The core of the algorithm is a classical Newton iteration procedure. New ingredients are needed, though, such as Kedlaya-Umans' modular composition algorithm and deflation techniques due to Lecerf.

Joint work with Esmaeil Mehrabi.