The computational complexity of polynomial factorization

May 15 to May 19, 2006

at the

American Institute of Mathematics, Palo Alto, California

organized by

Shuhong Gao, Mark van Hoeij, Erich Kaltofen, and Victor Shoup

Original Announcement

This workshop will be devoted to algorithms for factoring polynomials. Univariate and multivariate polynomials will be considered, with coefficients from finite fields, the rationals, and the complex numbers. Dense polynomials, where all coefficients are present, will be considered, as well as sparse polynomials that have many zero coefficients.

The problem of factoring polynomials is a classical problem of algebra with classical algorithms due to, for instance, Newton, Puisseux, Eisenstein, Gauss, Kronecker, Hilbert, and Hensel, and modern algorithms that use randomization, lattice basis reduction, baby-steps giant-steps techniques, root power and logarithmic derivates sums, and numerical approximation. Modern algorithms utilize efficient data structures such as straight-line programs and black boxes for evalution. The goal of the workshop is to invent significantly faster new algorithms, or in turn establish hardness of a given factorization problem.

The main topics for the workshop are:

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.