This talk presents joint work with J. Rosenkilde and G. Solomatov, about
new algorithms for bivariate multi-point evaluation, interpolation and
modular composition, which under certain assumptions have quasi-linear
complexity. For multi-point evaluation and interpolation we assume that
the set of points is generic and available for precomputation. In the
case of modular composition, similar assumptions are made on a bivariate
ideal which depends on part of the input. The key tool is an algorithm
that reshapes the degree bounds of a given bivariate polynomial while
preserving its membership in a coset of some fixed bivariate ideal
available for precomputation.
