Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields

DOI10.1145/2465506.2465514zbMath1360.68916arXiv1204.1113OpenAlexW2132291283MaRDI QIDQ2963217

Qi Cheng, J. Maurice Rojas, Jingguo Bi

Publication date: 10 February 2017

Published in: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.1113

zbMATH Keywords

square-freesolvabilityfinite fieldsdiscriminantgcdNP-hardnessresultantsparse polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Sparse univariate polynomials with many roots over finite fields ⋮ Bounded-degree factors of lacunary multivariate polynomials ⋮ Estimating the number of roots of trinomials over finite fields ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ Roots of sparse polynomials over a finite field ⋮ Computing the multilinear factors of lacunary polynomials without heights ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields

This page was built for publication: Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields