Approximate GCD of several univariate polynomials, small degree perturbations

International audienceWe consider the following computational problem, posed by von zur Gathen et al. [18]: given a family of generic univariate polynomials f := (f0 , ..., fs ), construct an algorithm to find polynomial purtubbations u :=(u0 , ..., us ) with "small" degrees such that the GCD (greater common divisor) of the perturbed family f + u has a "large" degree. In this paper, we propose an algorithm which solves this problem in polynomial time under a generic condition generalizing the normal degree sequence used in [18] for the case s = 1