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

Marek Karpinski, Igor Shparlinski

Research output: Chapter in Book/Report/Conference proceedingChapter

10 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 languageEnglish
Title of host publicationApplied Algebra, Algebraic Algorithms and Error-Correcting Codes - 13th International Symposium, AAECC-13, Proceedings
Subtitle of host publication13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings
EditorsMarc Fossorier, Hideki Imai, Shu Lin, Alain Poli
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages492-497
Number of pages6
ISBN (Electronic)9783540467960
ISBN (Print)9783540667230
DOIs
Publication statusPublished - 1999
Event13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999 - Honolulu, United States
Duration: 15 Nov 199919 Nov 1999

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume1719
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999
CountryUnited States
CityHonolulu
Period15/11/9919/11/99

Fingerprint Dive into the research topics of 'On the computational hardness of testing square-freeness of sparse polynomials'. Together they form a unique fingerprint.

  • 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). Berlin: Springer, Springer Nature. https://doi.org/10.1007/3-540-46796-3_47