On the complexity of factoring bivariate supersparse (lacunary) polynomials

DOI10.1145/1073884.1073914MaRDI QIDQ5262765zbMATH OpenOpenAlexFDO

Authors 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

NP-hardnessmultivariate polynomialspolynomial factorizationspolynomial-time complexitysparse polynomialslacunary polynomials

Mathematics Subject Classification ID

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

Recommendations

• Factoring bivariate sparse (lacunary) polynomials
• Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
• Factoring sparse multivariate polynomials
• Factoring bivariate lacunary polynomials without heights
• scientific article; zbMATH DE number 3887067

Cited in

(16)

• On a family of preimage-resistant functions
• Computing the multilinear factors of lacunary polynomials without heights
• On computing the degree of a Chebyshev polynomial from its value
• Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
• Factoring bivariate lacunary polynomials without heights
• Factorization of bivariate sparse polynomials
• A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum
• Factoring bivariate sparse (lacunary) polynomials
• New Sparse Multivariate Polynomial Factorization Algorithms over Integers
• scientific article; zbMATH DE number 3887067 (Why is no real title available?)
• Sparse bivariate polynomial factorization
• The number of roots of a lacunary bivariate polynomial on a line
• Some necessary clarifications about the chords' problem and the partial digest problem
• Bounded-degree factors of lacunary multivariate polynomials
• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• Lacunaryx: computing bounded-degree factors of lacunary polynomials

This page was built for publication: On the complexity of factoring bivariate supersparse (lacunary) polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262765)