On the complexity of factoring bivariate supersparse (Lacunary) polynomials

DOI10.1145/1073884.1073914zbMath1356.11092OpenAlexW2028346139MaRDI QIDQ5262765

Erich L. Kaltofen, Pascal Koiran

Publication date: 16 July 2015

Published in: Proceedings of the 2005 international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1073884.1073914

zbMATH Keywords

multivariate polynomialsNP-hardnesspolynomial factorizationspolynomial-time complexitysparse polynomialslacunary polynomials

Mathematics Subject Classification ID

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

Related Items

Bounded-degree factors of lacunary multivariate polynomials ⋮ Factoring bivariate sparse (lacunary) polynomials ⋮ A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum ⋮ New Sparse Multivariate Polynomial Factorization Algorithms over Integers ⋮ Lacunaryx ⋮ Sparse bivariate polynomial factorization ⋮ On computing the degree of a Chebyshev polynomial from its value ⋮ Computing the multilinear factors of lacunary polynomials without heights ⋮ On a family of preimage-resistant functions ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ The number of roots of a lacunary bivariate polynomial on a line ⋮ Some necessary clarifications about the chords' problem and the partial digest problem