On the computational hardness of testing square-freeness of sparse polynomials

Marek Karpinski; Igor Shparlinski

doi:10.1007/3-540-46796-3_47

On the computational hardness of testing square-freeness of sparse polynomials

Marek Karpinski, Igor Shparlinski

School of Computing

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

11 Citations (Scopus)

Abstract

We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field F p of p elements is NP-hard. We also discuss some related open problems about sparse polynomials.

Original language	English
Title of host publication	Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings
Subtitle of host publication	13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings
Editors	Marc Fossorier, Hideki Imai, Shu Lin, Alain Poli
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	492-497
Number of pages	6
ISBN (Electronic)	9783540467960
ISBN (Print)	9783540667230
DOIs	https://doi.org/10.1007/3-540-46796-3_47
Publication status	Published - 1999
Event	13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999 - Honolulu, United States Duration: 15 Nov 1999 → 19 Nov 1999

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	1719
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999
Country/Territory	United States
City	Honolulu
Period	15/11/99 → 19/11/99

Access to Document

10.1007/3-540-46796-3_47

Cite this

Karpinski, M., & Shparlinski, I. (1999). On the computational hardness of testing square-freeness of sparse polynomials. In M. Fossorier, H. Imai, S. Lin, & A. Poli (Eds.), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings (pp. 492-497). (Lecture Notes in Computer Science; Vol. 1719). Springer, Springer Nature. https://doi.org/10.1007/3-540-46796-3_47

Karpinski, Marek ; Shparlinski, Igor. / On the computational hardness of testing square-freeness of sparse polynomials. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. editor / Marc Fossorier ; Hideki Imai ; Shu Lin ; Alain Poli. Berlin : Springer, Springer Nature, 1999. pp. 492-497 (Lecture Notes in Computer Science).

@inbook{3f02602b6fe247838b8ea3a5377c62f7,

title = "On the computational hardness of testing square-freeness of sparse polynomials",

abstract = "We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field F p of p elements is NP-hard. We also discuss some related open problems about sparse polynomials.",

author = "Marek Karpinski and Igor Shparlinski",

year = "1999",

doi = "10.1007/3-540-46796-3_47",

language = "English",

isbn = "9783540667230",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Springer Nature",

pages = "492--497",

editor = "Marc Fossorier and Hideki Imai and Shu Lin and Alain Poli",

booktitle = "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings",

address = "United States",

note = "13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999 ; Conference date: 15-11-1999 Through 19-11-1999",

}

Karpinski, M & Shparlinski, I 1999, On the computational hardness of testing square-freeness of sparse polynomials. in M Fossorier, H Imai, S Lin & A Poli (eds), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. Lecture Notes in Computer Science, vol. 1719, Springer, Springer Nature, Berlin, pp. 492-497, 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999, Honolulu, Hawaii, United States, 15/11/99. https://doi.org/10.1007/3-540-46796-3_47

On the computational hardness of testing square-freeness of sparse polynomials. / Karpinski, Marek; Shparlinski, Igor.

Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. ed. / Marc Fossorier; Hideki Imai; Shu Lin; Alain Poli. Berlin : Springer, Springer Nature, 1999. p. 492-497 (Lecture Notes in Computer Science; Vol. 1719).

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

TY - CHAP

T1 - On the computational hardness of testing square-freeness of sparse polynomials

AU - Karpinski, Marek

AU - Shparlinski, Igor

PY - 1999

Y1 - 1999

N2 - We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field F p of p elements is NP-hard. We also discuss some related open problems about sparse polynomials.

AB - We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field F p of p elements is NP-hard. We also discuss some related open problems about sparse polynomials.

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

U2 - 10.1007/3-540-46796-3_47

DO - 10.1007/3-540-46796-3_47

M3 - Chapter

AN - SCOPUS:84957663373

SN - 9783540667230

T3 - Lecture Notes in Computer Science

SP - 492

EP - 497

BT - Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings

A2 - Fossorier, Marc

A2 - Imai, Hideki

A2 - Lin, Shu

A2 - Poli, Alain

PB - Springer, Springer Nature

CY - Berlin

T2 - 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999

Y2 - 15 November 1999 through 19 November 1999

ER -

Karpinski M, Shparlinski I. On the computational hardness of testing square-freeness of sparse polynomials. In Fossorier M, Imai H, Lin S, Poli A, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. Berlin: Springer, Springer Nature. 1999. p. 492-497. (Lecture Notes in Computer Science). https://doi.org/10.1007/3-540-46796-3_47

On the computational hardness of testing square-freeness of sparse polynomials

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this