Bit complexity for computing one point in each connected component of a smooth real algebraic set

DOI10.1016/j.jsc.2022.08.010OpenAlexW4289931776MaRDI QIDQ2100045

Éric Schost, Jesse Elliott, Mark W. Giesbrecht

Publication date: 21 November 2022

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

complexityNoether positionreal algebraic geometryweak transversality

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Computational aspects in algebraic geometry (14Qxx) Real algebraic and real-analytic geometry (14Pxx)

Uses Software

• ISOLATE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
• A baby step-giant step roadmap algorithm for general algebraic sets
• A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
• Definability and fast quantifier elimination in algebraically closed fields
• Solving systems of polynomial inequalities in subexponential time
• The complexity of partial derivatives
• Solving zero-dimensional systems through the rational univariate representation
• Lower bounds for diophantine approximations
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Straight-line programs in geometric elimination theory
• Effective equidimensional decomposition of affine varieties
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Sharp estimates for the arithmetic Nullstellensatz
• Bifurcations and catastrophes. Geometry of solutions to nonlinear problems. Transl. from the French by David Chillingworth
• On the geometry of polar varieties
• Generalized polar varieties: geometry and algorithms
• Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze
• Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
• On the Complexity of Computing Critical Points with Gröbner Bases
• Critical Point Computations on Smooth Varieties
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Ideals defined by matrices and a certain complex associated with them
• Polar classes of singular varieties
• Sharp estimates for triangular sets
• On the bit complexity of finding points in connected components of a smooth real hypersurface
• Algebraic Degree of Polynomial Optimization
• Algorithms in real algebraic geometry
• Polar varieties and efficient real elimination

This page was built for publication: Bit complexity for computing one point in each connected component of a smooth real algebraic set