@inbook{947cc2f03c3d4b929f0e1127530947a8,

title = "Approximate polynomial gcd: Small degree and small height perturbations",

abstract = "We consider the following computational problem: we are given two coprime univariate polynomials f 0 and f 1 over a ring 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 is an arbitrary field, in the generic case when f 0 and f 1 have a so-called normal degree sequence), and large height (when ).",

author = "{Von Zur Gathen}, Joachim and Shparlinski, {Igor E.}",

year = "2008",

doi = "10.1007/978-3-540-78773-0_24",

language = "English",

isbn = "9783540787723",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "276--283",

editor = "Laber, {Eduardo Sany} and Claudson Bornstein and Nogueira, {Loana Tito} and Luerbio Faria",

booktitle = "LATIN 2008: Theoretical Informatics",

address = "United States",

}