Approximate GCD of several univariate polynomials with small degree perturbations

摘要

We consider the following computational problem: given a family of generic univariate polynomials f := (f_0,...,f_s), construct an algorithm to find polynomial perturbations u := (u_0.....u_s) with "small" degrees such that the greater common divisor of the family of polynomials 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 for the case s = 1.