Department of Mathematics and Computer Science, City University of New York.

Solution of Polynomial Equations

The classical problem of solving polynomial equations has history of four millennia and largely motivated the development of mathematics and applied mathematics throughout several centuries. Recently several effective methods have been developed for this problem, which enabled its solution in nearly optimal time (within polylogarithmic factors), both in arithmetic and Boolean measurements and under both sequential and parallel models of computing. Some of the techniques developed for this problem allow their extension to the solution of polynomial systems of equation where their combination with some other techniques yielded acceleration of the known methods by order of magnitude. (The latter part is joint work with Bernard Mourrain.)