Factoring bivariate sparse (lacunary) polynomials

DOI10.1016/j.jco.2006.06.002zbMath1170.12004arXivmath/0602145OpenAlexW2072221429MaRDI QIDQ883330

Martín Sombra, Teresa Krick, Martín Avendano

Publication date: 4 June 2007

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

polynomial factorizationLehmer's problemheight of pointslacunary (sparse) polynomials

Mathematics Subject Classification ID

Related Items (12)

Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations ⋮ Bounded-degree factors of lacunary multivariate polynomials ⋮ A lifting and recombination algorithm for rational factorization of sparse polynomials ⋮ Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time ⋮ Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\) ⋮ Algebraic osculation and application to factorization of sparse polynomials ⋮ Sparse bivariate polynomial factorization ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ Successive minima of toric height functions ⋮ Factorization of bivariate sparse polynomials ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sur des hauteurs alternatives. I. (On alternative heights. I)
• Factoring polynomials with rational coefficients
• A polynomial time algorithm for diophantine equations in one variable
• Factoring multivariate integral polynomials
• Effective Noether irreducibility forms and applications
• Improved dense multivariate polynomial factorization algorithms
• On Hensel factorization. I
• Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
• Algebraic Numbers Close to Both 0 and 1
• On a question of Lehmer and the number of irreducible factors of a polynomial
• Minoration effective de la hauteur des points d'une courbe de G_m²définie sur Q
• GEOMETRIC LOWER BOUNDS FOR THE NORMALIZED HEIGHT OF HYPERSURFACES
• Quelques Aspects Diophantiens des VariéTés Toriques Projectives
• Factoring Polynomials over Algebraic Number Fields
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Factoring Multivariate Polynomials over Algebraic Number Fields
• MINORATION DE LA HAUTEUR NORMALISE DANS UN TORE
• Minoration de la hauteur normalisée des hypersurfaces
• An effective lower bound for the height of algebraic numbers
• On the complexity of factoring bivariate supersparse (Lacunary) polynomials
• Factoring Polynomials Over Large Finite Fields

This page was built for publication: Factoring bivariate sparse (lacunary) polynomials