On the complexity of factoring bivariate supersparse (lacunary) polynomials

DOI10.1145/1073884.1073914zbMATH Open1356.11092OpenAlexW2028346139MaRDI QIDQ5262765FDOQ5262765

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

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

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)

Cited In (16)

• On a family of preimage-resistant functions
• Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
• Factoring bivariate lacunary polynomials without heights
• Computing the multilinear factors of lacunary polynomials without heights
• On computing the degree of a Chebyshev polynomial from its value
• 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
• Title not available (Why is that?)
• 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
• Lacunaryx: computing bounded-degree factors of lacunary polynomials
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

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)