Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Winter 2007/2008 

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

Imprint, webmaster & more