Approximate polynomial GCD: small degree and small height perturbations
Joachim von zur Gathen (cosec - b-it)
Thursday, 7 February, 2008, 15:00 sharp (s.t), b-it 1.25 (cosec meeting room)
We consider the following computational problem: we are given two coprime univariate polynomials f0 and f1 over a ring R and want to find whether after a small perturbation we can achieve a large GCD.
We solve this problem in polynomial time for two notions of ``large'' (and ``small''): large degree (when R = F is an arbitrary field, in the generic case when f0 and f1 have a so-called normal degree sequence), and large height (when R = Z).
Key words: Euclidean algorithm, GCD, approximate computation