The computational complexity of polynomial factorization
May 15 to May 19, 2006
at the
American Institute of Mathematics,
San Jose, 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:
- 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.
Material from the workshop
A list of participants.
The workshop schedule.
A report on the workshop activities.