Approximate polynomial gcd: Small degree and small height perturbations

Joachim Von Zur Gathen; Igor E. Shparlinski

doi:10.1007/978-3-540-78773-0_24

Approximate polynomial gcd: Small degree and small height perturbations

Joachim Von Zur Gathen^*, Igor E. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

3 Citations (Scopus)

Abstract

We consider the following computational problem: we are given two coprime univariate polynomials f ₀ and f ₁ 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 ₀ and f ₁ have a so-called normal degree sequence), and large height (when ).

Original language	English
Title of host publication	LATIN 2008: Theoretical Informatics
Subtitle of host publication	8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings
Editors	Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	276-283
Number of pages	8
ISBN (Electronic)	9783540787730
ISBN (Print)	9783540787723
DOIs	https://doi.org/10.1007/978-3-540-78773-0_24
Publication status	Published - 2008
Event	8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil Duration: 7 Apr 2008 → 11 Apr 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Berlin Heidelberg
Volume	4957
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	8th Latin American TheoreticalINformatics Symposium, LATIN 2008
Country/Territory	Brazil
City	Buzios
Period	7/04/08 → 11/04/08

Access to Document

10.1007/978-3-540-78773-0_24

Cite this

Von Zur Gathen, J., & Shparlinski, I. E. (2008). Approximate polynomial gcd: Small degree and small height perturbations. In E. S. Laber, C. Bornstein, L. T. Nogueira, & L. Faria (Eds.), LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings (pp. 276-283). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4957). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-78773-0_24

Von Zur Gathen, Joachim ; Shparlinski, Igor E. / Approximate polynomial gcd : Small degree and small height perturbations. LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings. editor / Eduardo Sany Laber ; Claudson Bornstein ; Loana Tito Nogueira ; Luerbio Faria. Berlin : Springer, Springer Nature, 2008. pp. 276-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

note = "8th Latin American TheoreticalINformatics Symposium, LATIN 2008 ; Conference date: 07-04-2008 Through 11-04-2008",

}

Von Zur Gathen, J & Shparlinski, IE 2008, Approximate polynomial gcd: Small degree and small height perturbations. in ES Laber, C Bornstein, LT Nogueira & L Faria (eds), LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4957, Springer, Springer Nature, Berlin, pp. 276-283, 8th Latin American TheoreticalINformatics Symposium, LATIN 2008, Buzios, Brazil, 7/04/08. https://doi.org/10.1007/978-3-540-78773-0_24

Approximate polynomial gcd: Small degree and small height perturbations. / Von Zur Gathen, Joachim; Shparlinski, Igor E.
LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings. ed. / Eduardo Sany Laber; Claudson Bornstein; Loana Tito Nogueira; Luerbio Faria. Berlin: Springer, Springer Nature, 2008. p. 276-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4957).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Approximate polynomial gcd

T2 - 8th Latin American TheoreticalINformatics Symposium, LATIN 2008

AU - Von Zur Gathen, Joachim

AU - Shparlinski, Igor E.

PY - 2008

Y1 - 2008

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

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

UR - http://www.scopus.com/inward/record.url?scp=43049150423&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78773-0_24

DO - 10.1007/978-3-540-78773-0_24

M3 - Chapter

AN - SCOPUS:43049150423

SN - 9783540787723

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 276

EP - 283

BT - LATIN 2008: Theoretical Informatics

A2 - Laber, Eduardo Sany

A2 - Bornstein, Claudson

A2 - Nogueira, Loana Tito

A2 - Faria, Luerbio

PB - Springer, Springer Nature

CY - Berlin

Y2 - 7 April 2008 through 11 April 2008

ER -

Von Zur Gathen J, Shparlinski IE. Approximate polynomial gcd: Small degree and small height perturbations. In Laber ES, Bornstein C, Nogueira LT, Faria L, editors, LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings. Berlin: Springer, Springer Nature. 2008. p. 276-283. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-78773-0_24

Approximate polynomial gcd: Small degree and small height perturbations

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this