On the bit complexity of polynomial system solving

DOI10.1016/j.jco.2018.09.005zbMath1432.13020arXiv1612.07786MaRDI QIDQ1734694

Guillermo Matera, Nardo Giménez

Publication date: 27 March 2019

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

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

zbMATH Keywords

Chow form; bit complexity; lucky primes; lifting fibers; polynomial system solving over \(\mathbb{Q}\); reduced regular sequence

Mathematics Subject Classification ID

65H10: Numerical computation of solutions to systems of equations

65Y20: Complexity and performance of numerical algorithms

13P15: Solving polynomial systems; resultants

Related Items

On the complexity exponent of polynomial system solving

Uses Software

• Kronecker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quiz games as a model for information hiding
• Polynomial equation solving by lifting procedures for ramified fibers
• Deformation techniques to solve generalised Pham systems
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Definability and fast quantifier elimination in algebraically closed fields
• Diophantine approximation on abelian varieties
• Introduction to the solution of polynomial systems
• Deformation techniques for sparse systems
• EUROCAL '85. European Conference on Computer Algebra, Linz, Austria, April 1-3, 1985. Proceedings. Vol. 2: Research contributions
• Résolution des systèmes d'équations algébriques
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• Lower bounds for diophantine approximations
• Straight-line programs in geometric elimination theory
• The hardness of polynomial equation solving
• Computing parametric geometric resolutions
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Sharp estimates for the arithmetic Nullstellensatz
• Algebraic Geometry. I: Complex projective varieties.
• On the intrinsic complexity of the arithmetic Nullstellensatz
• Deformation techniques for efficient polynomial equation solving.
• A concise proof of the Kronecker polynomial system solver from scratch
• Lower complexity bounds for interpolation algorithms
• Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
• SHARPER COMPLEXITY BOUNDS FOR ZERO-DIMENSIONAL GRÖBNER BASES AND POLYNOMIAL SYSTEM SOLVING
• Fast computation of a rational point of a variety over a finite field
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Complexity of standard bases in projective dimension zero
• A Gröbner free alternative for polynomial system solving