Computing the homology of semialgebraic sets. I: Lax formulas
From MaRDI portal
Publication:2291730
DOI10.1007/s10208-019-09418-yzbMath1440.14264arXiv1807.06435OpenAlexW3103556238WikidataQ127928446 ScholiaQ127928446MaRDI QIDQ2291730
Josué Tonelli-Cueto, Peter Bürgisser, Felipe Cucker
Publication date: 31 January 2020
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.06435
Analysis of algorithms and problem complexity (68Q25) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Semialgebraic sets and related spaces (14P10) Complexity and performance of numerical algorithms (65Y20)
Related Items (9)
Functional norms, condition numbers and numerical algorithms in algebraic geometry ⋮ On the complexity of the Plantinga-Vegter algorithm ⋮ The critical curvature degree of an algebraic variety ⋮ Sampling and homology via bottlenecks ⋮ Persistent Homology of Semialgebraic Sets ⋮ Efficient simplicial replacement of semialgebraic sets ⋮ Computing the homology of semialgebraic sets. II: General formulas ⋮ Smoothed analysis for the condition number of structured real polynomial systems ⋮ Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
Uses Software
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
- A numerical algorithm for zero counting. III: Randomization and condition
- On a problem posed by Steve Smale
- Computing the homology of real projective sets
- An introduction to homological algebra
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Exotic quantifiers, complexity classes, and complete problems
- Complexity theory of numerical linear algebra
- Solving systems of polynomial inequalities in subexponential time
- Constructing roadmaps of semi-algebraic sets. I: Completeness
- A survey of motion planning and related geometric algorithms
- 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
- Counting connected components of a semialgebraic set in subexponential time
- Topological stability of smooth mappings
- Complexity of deciding Tarski algebra
- Complexity of Bezout's theorem. V: Polynomial time
- Mathematical problems for the next century
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Polynomial inequalities representing polyhedra
- Approximate zeros and condition numbers
- The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
- Average-case complexity without the black swans
- Complexity of Bezout's theorem. III: Condition number and packing
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- Computing the first few Betti numbers of semi-algebraic sets in single exponential time
- Finding the homology of submanifolds with high confidence from random samples
- Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
- Computing Roadmaps of General Semi-Algebraic Sets
- Complexity estimates depending on condition and round-off error
- Curvature Measures
- Neighborhoods of Algebraic Sets
- The “λ-medial axis”
- The probability that a slightly perturbed numerical analysis problem is difficult
- The Probability That a Numerical Analysis Problem is Difficult
- Complexity of Bezout's Theorem I: Geometric Aspects
- On the combinatorial and algebraic complexity of quantifier elimination
- Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time
- Computing roadmaps of semi-algebraic sets on a variety
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Notes on Topological Stability
- Weak feature size and persistent homology
- Ensembles et morphismes stratifiés
- A New Proof of Brown's Collaring Theorem
- Numerical inverting of matrices of high order
- ROUNDING-OFF ERRORS IN MATRIX PROCESSES
- Numerical Inverting of Matrices of High Order. II
- Locally flat imbeddings of topological manifolds
- Finding connected components of a semialgebraic set in subexponential time
This page was built for publication: Computing the homology of semialgebraic sets. I: Lax formulas
