Approximate polynomial gcd

Small degree and small height perturbations

Joachim Von Zur Gathen*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

3 Citations (Scopus)


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 ).

Original languageEnglish
Title of host publicationLATIN 2008: Theoretical Informatics
Subtitle of host publication8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings
EditorsEduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Number of pages8
ISBN (Electronic)9783540787730
ISBN (Print)9783540787723
Publication statusPublished - 2008
Event8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil
Duration: 7 Apr 200811 Apr 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th Latin American TheoreticalINformatics Symposium, LATIN 2008

Fingerprint Dive into the research topics of 'Approximate polynomial gcd: Small degree and small height perturbations'. Together they form a unique fingerprint.

Cite this