The computational complexity of polynomial factorization

This workshop, sponsored by AIM and the NSF, 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:

• The fastest-known asymptotic running times of algorithms for factoring univariate and multivariate polynomials over finite fields, the rational and the complex numbers in dense and sparse representation.
• Approximate factorization of multivariate polynomials over the complex numbers whose coefficients may be given approximately due to errors caused by physical measurements or by floating point computation.
• NP-hardness of irreducibility and root finding of polynomials in sparse and straight-line representation over finite fields and the rational numbers.
• Algorithms for computing the Galois group of a univariate polynomials over the rational numbers.

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email workshops@aimath.org

Plain text announcement or brief announcement.

This page has been translated into the Serbo-Croatian language by Jovana Milutinovich, into the Punjabi language by the Bydiscountcodes Team, into the Finnish language by Fijavan Brenk, and into the Urdu and Sinhi languages by Samuel Badree.

Go to the American Institute of Mathematics.
Return to the AIM Research Conference Center.