1. Amelunxen, D., Lotz, M.: Average-case complexity without the black swans. J. Complexity41, 82–101 (2017)

   Article MathSciNet MATH  Google Scholar 

2. Basu, S.: On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets. In: Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), pp. 408–417. ACM, New York (1996)

   Google Scholar 

3. Basu, S.: Computing the first few Betti numbers of semi-algebraic sets in single exponential time. J. Symbolic Comput.41(10), 1125–1154 (2006)

   Article MathSciNet MATH  Google Scholar 

4. Basu, S., Pollack, R., Roy, M.F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM43, 1002–1045 (1996)

   Article MathSciNet MATH  Google Scholar 

5. Basu, S., Pollack, R., Roy, M.F.: Computing roadmaps of semi-algebraic sets on a variety. J. AMS33, 55–82 (1999)

   MATH  Google Scholar 

6. Basu, S., Pollack, R., Roy, M.F.: Algorithms in real algebraic geometry. Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Berlin (2006)

   Book MATH  Google Scholar 

7. Benedetti, R., Risler, J.J.: Real Algebraic and Semi-algebraic Sets, Hermann (1990)

   Google Scholar 

8. Bochnak, J., Coste, M., Roy, M.F.: Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge/A Series of Modern Surveys in Mathematics, vol. 36. Springer, Heidelberg (1998).https://doi.org/10.1007/978-3-662-03718-8. Translated from the 1987 French original, Revised by the authors

   Book MATH  Google Scholar 

9. Bürgisser, P., Cucker, F.: Condition. Grundlehren der mathematischen Wissenschaften, vol. 349. Springer, Heidelberg (2013).https://doi.org/10.1007/978-3-642-38896-5

   Book MATH  Google Scholar 

10. Bürgisser, P., Cucker, F., Lairez, P.: Computing the homology of basic semialgebraic sets in weakly exponential time. J. ACM66(1), 5:1–5:30 (2019)

    Article MATH  Google Scholar 

11. Bürgisser, P., Cucker, F., Lotz, M.: The probability that a slightly perturbed numerical analysis problem is difficult. Math. Comput.77, 1559–1583 (2008)

    Article MathSciNet MATH  Google Scholar 

12. Bürgisser, P., Cucker, F., Tonelli-Cueto, J.: Computing the homology of semialgebraic sets. I: Lax formulas. Found. Comput. Math.arXiv:1807.06435 (2018)

13. Bürgisser, P., Cucker, F., Tonelli-Cueto, J.: Computing the homology of semialgebraic sets. II: Arbitrary formulas (2019). preprint

    Google Scholar 

14. Canny, J.: Computing roadmaps of general semi-algebraic sets. Comput. J.36(5), 504–514 (1993)

    Article MathSciNet MATH  Google Scholar 

15. Canny, J., Grigorev, D., Vorobjov, N.: Finding connected components of a semialgebraic set in subexponential time. Appl. Algebra Eng. Commun. Comput.2(4), 217–238 (1992)

    Article MathSciNet  Google Scholar 

16. Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 134–183. Springer, Heidelberg (1975).https://doi.org/10.1007/3-540-07407-4_17

    Chapter  Google Scholar 

17. Cucker, F.: Approximate zeros and condition numbers. J. Complexity15, 214–226 (1999)

    Article MathSciNet MATH  Google Scholar 

18. Cucker, F., Krick, T., Shub, M.: Computing the homology of real projective sets. Found. Comp. Math.18, 929–970 (2018)

    Article MathSciNet MATH  Google Scholar 

19. Cucker, F., Smale, S.: Complexity estimates depending on condition and round-off error. J. ACM46, 113–184 (1999)

    Article MathSciNet MATH  Google Scholar 

20. Demmel, J.: The probability that a numerical analysis problem is difficult. Math. Comput.50, 449–480 (1988)

    Article MathSciNet MATH  Google Scholar 

21. Gabrielov, A., Vorobjov, N.: Approximation of definable sets by compact families, and upper bounds on homotopy and homology. J. Lond. Math. Soc.80(1), 35–54 (2009)

    Article MathSciNet MATH  Google Scholar 

22. Goldstine, H., von Neumann, J.: Numerical inverting matrices of high order, II. Proc. AMS2, 188–202 (1951)

    Article MathSciNet MATH  Google Scholar 

23. Grigoriev, D.: Complexity of deciding Tarski algebra. J. Symbolic Comput.5, 65–108 (1988)

    Article MathSciNet MATH  Google Scholar 

24. Grigoriev, D., Vorobjov, N.: Solving systems of polynomial inequalities in subexponential time. J. Symbolic Comput.5, 37–64 (1988)

    Article MathSciNet MATH  Google Scholar 

25. Grigoriev, D., Vorobjov, N.: Counting connected components of a semialgebraic set in subexponential time. Comput. Complexity2, 133–186 (1992)

    Article MathSciNet MATH  Google Scholar 

26. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)

    MATH  Google Scholar 

27. Heintz, J., Roy, M.F., Solerno, P.: Single exponential path finding in semi-algebraic sets II: the general case. In: Bajaj, C. (ed.) Algebraic Geometry and its Applications, pp. 449–465. Springer, New York (1994).https://doi.org/10.1007/978-1-4612-2628-4_28

    Chapter MATH  Google Scholar 

28. Koiran, P.: The real dimension problem is\({\sf N}P_{\mathbb{R}}\)-complete. J. Complexity15, 227–238 (1999)

    Article MathSciNet MATH  Google Scholar 

29. Kostlan, E.: Complexity theory of numerical linear algebra. J. Comput. Appl. Math.22, 219–230 (1988)

    Article MathSciNet MATH  Google Scholar 

30. von Neumann, J., Goldstine, H.: Numerical inverting matrices of high order. Bull. AMS53, 1021–1099 (1947)

    Article MathSciNet MATH  Google Scholar 

31. Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom.39, 419–441 (2008)

    Article MathSciNet MATH  Google Scholar 

32. Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. Part I. J. Symbolic Comput.13, 255–299 (1992)

    Article MathSciNet MATH  Google Scholar 

33. Renegar, J.: Some perturbation theory for linear programming. Math. Program.65, 73–91 (1994)

    Article MathSciNet MATH  Google Scholar 

34. Renegar, J.: Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim.5, 506–524 (1995)

    Article MathSciNet MATH  Google Scholar 

35. Renegar, J.: Linear programming, complexity theory and elementary functional analysis. Math. Program.70, 279–351 (1995)

    MathSciNet MATH  Google Scholar 

36. Shub, M., Smale, S.: Complexity of Bézout’s theorem I: geometric aspects. J. AMS6, 459–501 (1993)

    MATH  Google Scholar 

37. Smale, S.: Complexity theory and numerical analysis. In: Iserles, A. (ed.) Acta Numerica, pp. 523–551. Cambridge University Press (1997)

    Google Scholar 

38. Spielman, D., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM52(10), 77–84 (2009)

    Article  Google Scholar 

39. Tarski, A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley (1951)

    MATH  Google Scholar 

40. Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc.S2–42, 230–265 (1936)

    MathSciNet MATH  Google Scholar 

41. Turing, A.: Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math.1, 287–308 (1948)

    Article MathSciNet MATH  Google Scholar 

42. Wilkinson, J.: Some comments from a numerical analyst. J. ACM18, 137–147 (1971)

    Article MathSciNet MATH  Google Scholar 

43. Wüthrich, H.R.: Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper. In: Strassen, V., Specker, E. (eds.) Komplexität von Entscheidungsproblemen Ein Seminar. LNCS, vol. 43, pp. 138–162. Springer, Heidelberg (1976).https://doi.org/10.1007/3-540-07805-3_10

    Chapter  Google Scholar 

Download references