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

Marek Karpinski, Igor Shparlinski

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

13 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
Country/TerritoryUnited 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.
  • Preface

    Boztaş, S. & Shparlinski, I. E., 2001, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 14th International Symposium, AAECC-14, Melbourne, Australia, November 26-30, 2001. Proceedings. Boztas, S. & Shparlinski, I. E. (eds.). Berlin, p. v-vi 2 p. (Lecture Notes in Computer Science; vol. 2227).

    Research output: Chapter in Book/Report/Conference proceedingForeword/postscript/introductionpeer-review

Cite this