Solving systems of polynomial inequalities in subexponential time
From MaRDI portal
algebraic complexityreal solutions of systems of polynomial inequalitiessubexponential time algorithm
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials (irreducibility, etc.) (11R09) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Real algebraic and real-analytic geometry (14Pxx) Software, source code, etc. for problems pertaining to field theory (12-04)
Recommendations
Cites work
- scientific article; zbMATH DE number 3870491 (Why is no real title available?)
- scientific article; zbMATH DE number 3906595 (Why is no real title available?)
- scientific article; zbMATH DE number 3959582 (Why is no real title available?)
- scientific article; zbMATH DE number 3982411 (Why is no real title available?)
- scientific article; zbMATH DE number 4092769 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3564960 (Why is no real title available?)
- scientific article; zbMATH DE number 3627912 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 3804835 (Why is no real title available?)
- scientific article; zbMATH DE number 3445379 (Why is no real title available?)
- scientific article; zbMATH DE number 3893304 (Why is no real title available?)
- scientific article; zbMATH DE number 3893305 (Why is no real title available?)
- scientific article; zbMATH DE number 3895043 (Why is no real title available?)
- scientific article; zbMATH DE number 3221041 (Why is no real title available?)
- scientific article; zbMATH DE number 3307642 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- An Inequality About Factors of Polynomials
- Definability and fast quantifier elimination in algebraically closed fields
- Integer Arithmetic Algorithms for Polynomial Real Zero Determination
- On the Betti Numbers of Real Varieties
Cited in
(only showing first 100 items - show all)- Stability analysis of a bacterial growth model through computer algebra
- Intrinsic complexity estimates in polynomial optimization
- Involutions of polynomially parametrized surfaces
- A lower bound for randomized algebraic decision trees
- Bounds on the number of connected components for tropical prevarieties
- Fixed points, Nash equilibria, and the existential theory of the reals
- Bounding the radii of balls meeting every connected component of semi-algebraic sets
- Complexity of computing the local dimension of a semialgebraic set
- An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
- On a theory of computation and complexity over the real numbers: đđ- completeness, recursive functions and universal machines
- Description of the connected components of a semialgebraic set in single exponential time
- Cylindrical algebraic decomposition using local projections
- Semidefinite approximations of projections and polynomial images of semialgebraic sets
- Centerpoints: a link between optimization and convex geometry
- Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
- Cooperating techniques for solving nonlinear real arithmetic in the \texttt{cvc5} SMT solver (system description)
- Elementary recursive quantifier elimination based on Thom encoding and sign determination
- Combined Decision Techniques for the Existential Theory of the Reals
- Randomization and the computational power of analytic and algebraic decision trees
- Recent advances in real geometric reasoning
- Matrices in elimination theory
- Smooth points on semi-algebraic sets
- Deciding consistency of systems of exponential-polynomial inequalities in subexponential time
- On the Complexity of Equilibrium Computation in First-Price Auctions
- Exponentially more concise quantum recognition of non-RMM regular languages
- A finite algorithm for the realizabilty of a Delaunay triangulation
- Feasibility testing for systems of real quadratic equations
- Finding irreducible components of some real transcendental varieties
- Computational algebraic geometry of projective configurations
- Complexity lower bounds for computation trees with elementary transcendental function gates
- The complexity of the Hausdorff distance
- Systole length in hyperbolic \(n\)-manifolds
- A bibliography of quantifier elimination for real closed fields
- An algorithm for sums of squares of real polynomials
- The complexity of point configurations
- An algorithmic approach to Rupertâs problem
- Links with splitting number one
- Segment representations with small resolution
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- The complexity of positive semidefinite matrix factorization
- Un procédé d'élimination effective et quelques applications. (A procedure for effective elimination and some applications.)
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- Sur la complexité du principe de Tarski-Seidenberg
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Grid methods in computational real algebraic (and semialgebraic) geometry
- Oscillation of linear ordinary differential equations: on a theorem of A. Grigoriev
- Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
- Polar varieties, real equation solving, and data structures: the hypersurface case
- Some lower bounds for the complexity of the linear programming feasibility problem over the reals
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- Efficiently and effectively recognizing toricity of steady state varieties
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Complexity of deciding Tarski algebra
- On the intrinsic complexity of point finding in real singular hypersurfaces
- Proving inequalities and solving global optimization problems via simplified CAD projection
- Finding connected components of a semialgebraic set in subexponential time
- When a system of real quadratic equations has a solution
- On exact Reznick, Hilbert-Artin and Putinar's representations
- Identifying the parametric occurrence of multiple steady states for some biological networks
- The number of bits needed to represent a unit disk graph
- On the geometry of polar varieties
- Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping
- Deformation techniques for efficient polynomial equation solving.
- A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
- Nonrealizability proofs in computational geometry
- RAC-Drawability is ââ-complete and Related Results
- Generalized polar varieties and an efficient real elimination.
- Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
- Polynomial-time approximation schemes for circle and other packing problems
- Sublinear P system solutions to NP-complete problems
- Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set
- Computing Amoebas
- Computing final polynomials and final syzygies using Buchberger's Gröbner bases method
- Decomposition plans for geometric constraint systems. I: Performance measures for CAD
- Polynomial bounds for the oscillation of solutions of Fuchsian systems
- MRHS Equation Systems that can be Solved in Polynomial Time
- On the computation of the homology of semialgebraic sets
- Generalized polar varieties: geometry and algorithms
- Finding at least one point in each connected component of a real algebraic set defined by a single equation
- Minimizing polynomials via sum of squares over the gradient ideal
- Conormal spaces and Whitney stratifications
- Construction of roadmaps in semi-algebraic sets
- Faster real root decision algorithm for symmetric polynomials
- Real solving for positive dimensional systems.
- A survey of satisfiability modulo theory
- An approximate characterisation of the set of feasible trajectories for constrained flat systems
- Smoothing of real algebraic hypersurfaces by rigid isotopies
- Recent improvements in the complexity of the effective Nullstellensatz
- scientific article; zbMATH DE number 7559105 (Why is no real title available?)
- Complexity of stratifications of semi-Pfaffian sets
- A polynomial-time algorithm for computing low CP-rank decompositions
- Counting connected components of a semialgebraic set in subexponential time
- On the number of topological types occurring in a parameterized family of arrangements
- Numerically computing real points on algebraic sets
- Approximation schemes for geometric knapsack for packing spheres and fat objects
- Computing the homology of semialgebraic sets. I: Lax formulas
- Condition number based complexity estimate for computing local extrema
- A PTAS for the disk cover problem of geometric objects
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- Complexity of cylindrical decompositions of sub-Pfaffian
This page was built for publication: Solving systems of polynomial inequalities in subexponential time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113939)
