]. S. Arora, R. Ge, R. Kannan, and A. Moitra, Computing a nonnegative matrix factorization? provably, Proceedings of the 44th symposium on Theory of Computing, pp.145-162, 2012.

M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, 1969.

B. Bank, M. Giusti, J. Heintz, and G. Mbakop, Polar Varieties, Real Equation Solving, and Data Structures: The Hypersurface Case, Journal of Complexity, vol.13, issue.1, pp.5-27, 1997.
DOI : 10.1006/jcom.1997.0432

B. Bank, M. Giusti, J. Heintz, and L. Pardo, Generalized polar varieties: geometry and algorithms, Journal of Complexity, vol.21, issue.4, pp.377-412, 2005.
DOI : 10.1016/j.jco.2004.10.001
URL : http://doi.org/10.1016/j.jco.2004.10.001

B. Bank, M. Giusti, J. Heintz, M. Safey-el-din, and E. Schost, On the geometry of polar varieties, Applicable Algebra in Engineering, Communication and Computing, vol.43, issue.2, 2010.
DOI : 10.1007/s00200-009-0117-1
URL : https://hal.archives-ouvertes.fr/hal-01148162

S. Barone and S. Basu, Refined Bounds on the Number of Connected Components of Sign Conditions on a Variety, Discrete & Computational Geometry, vol.133, issue.2, pp.577-597, 2012.
DOI : 10.1007/s00454-011-9391-3

S. Barone and S. Basu, Refined bounds on the number of connected components of sign conditions II. arXiv preprint, 2013.

S. Basu, On bounding the Betti numbers and computing the Euler characteristic of semialgebraic sets, Proc. 28-th annual ACM Symposium on Theory of Computing, pp.408-417, 1996.

S. Basu, Computing the first few Betti numbers of semi-algebraic sets in single exponential time, Journal of Symbolic Computation, vol.41, issue.10, pp.1125-1154, 2006.
DOI : 10.1016/j.jsc.2006.07.001

S. Basu, R. Pollack, and M. Roy, Computing roadmaps of semi-algebraic sets (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , STOC '96, pp.168-173, 1996.
DOI : 10.1145/237814.237857

S. Basu, R. Pollack, and M. Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM, vol.43, issue.6, pp.1002-1045, 1996.
DOI : 10.1145/235809.235813

S. Basu, R. Pollack, and M. Roy, Computing the first Betti number and the connected components of semi-algebraic sets, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing , STOC '05, pp.304-312, 2005.
DOI : 10.1145/1060590.1060636

S. Basu, R. Pollack, and M. Roy, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, vol.10, 2006.
DOI : 10.1007/978-3-662-05355-3
URL : https://hal.archives-ouvertes.fr/hal-01083587

S. Basu, R. Pollack, and M. Roy, Computing the dimension of a semi-algebraic set, Journal of Mathematical Sciences, vol.134, issue.5, pp.2346-2353, 2006.
DOI : 10.1007/s10958-006-0111-0

S. Basu and M. Roy, Bounding the radii of balls meeting every connected component of semi-algebraic sets, Journal of Symbolic Computation, vol.45, issue.12, pp.1270-1279, 2010.
DOI : 10.1016/j.jsc.2010.06.009
URL : https://hal.archives-ouvertes.fr/hal-00459481

L. Blum, M. Shub, and S. Smale, On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines, [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pp.387-397, 1988.
DOI : 10.1109/SFCS.1988.21955

L. E. Blume and W. R. Zame, The Algebraic Geometry of Perfect and Sequential Equilibrium, Econometrica, vol.62, issue.4, pp.783-794, 1994.
DOI : 10.2307/2951732

J. Bochnak, M. Coste, and M. Roy, Géométrie algébrique réelle, 1987.

J. Bochnak, M. Coste, and M. Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete, 1998.
DOI : 10.1007/978-3-662-03718-8

J. Canny, The complexity of robot motion planning, 1987.

K. Chatterjee, R. Majumdar, and T. Henzinger, Stochastic limit-average games are in EXPTIME, International Journal of Game Theory, vol.158, issue.2, pp.219-234, 2008.
DOI : 10.1007/s00182-007-0110-5

A. Chistov, H. Fournier, L. Gurvits, and P. Koiran, Vandermonde Matrices, NP-Completeness, and Transversal Subspaces, Foundations of Computational Mathematics, vol.3, issue.4, pp.421-427, 2003.
DOI : 10.1007/s10208-002-0076-4

A. L. Chistov, Polynomial-Time Computation of the Dimension of Algebraic Varieties in Zero-Characteristic, Journal of Symbolic Computation, vol.22, issue.1, pp.1-25, 1996.
DOI : 10.1006/jsco.1996.0039

G. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decompostion, Automata Theory and Formal Languages, pp.134-183, 1975.
DOI : 10.1007/3-540-07407-4_17

D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics, vol.150, 1995.

M. Giusti and J. Heintz, La détermination de la dimension et des points isolées dune variété algébrique peuvent s effectuer en temps polynomial, Computational Algebraic Geometry and Commutative Algebra, pp.216-256, 1991.

M. Golubitsky, V. Guillemin, and M. Golubitsky, Stable mappings and their singularities, 1973.
DOI : 10.1007/978-1-4615-7904-5

D. Y. Grigor-'ev, Complexity of deciding Tarski algebra, Journal of Symbolic Computation, vol.5, issue.1-2, pp.65-108, 1988.
DOI : 10.1016/S0747-7171(88)80006-3

D. Y. Grigor-'ev and N. V. Jr, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, vol.5, issue.1-2, pp.37-64, 1988.
DOI : 10.1016/S0747-7171(88)80005-1

L. Guth and N. H. Katz, Algebraic methods in discrete analogs of the Kakeya problem, Advances in Mathematics, vol.225, issue.5, pp.2828-2839, 2010.
DOI : 10.1016/j.aim.2010.05.015

K. A. Hansen, M. Koucky, N. Lauritzen, P. B. Miltersen, and E. P. Tsigaridas, Exact algorithms for solving stochastic games, Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC '11, pp.205-214, 2011.
DOI : 10.1145/1993636.1993665

J. Heintz, M. Roy, and P. Solernó, Single exponential path finding in semi-algebraic sets II: The general case. In Algebraic geometry and its applications, collections of papers from Abhyankar's 60-th birthday conference, 1994.

Q. Jin and T. Yang, Overconstraint analysis on spatial 6-link loops. Mechanism and machine theory, pp.267-278, 2002.

H. Kaplan, J. Matousek, and M. Sharir, Simple Proofs of Classical Theorems in Discrete Geometry via the Guth???Katz Polynomial Partitioning Technique, Discrete & Computational Geometry, vol.133, issue.70, pp.1-19, 2011.
DOI : 10.1007/s00454-012-9443-3

P. Koiran, Randomized and deterministic algorithms for the dimension of algebraic varieties, Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.36-45, 1997.
DOI : 10.1109/SFCS.1997.646091

P. Koiran, The Real Dimension Problem Is NPR-Complete, Journal of Complexity, vol.15, issue.2, pp.227-238, 1999.
DOI : 10.1006/jcom.1999.0502

A. Logar, A computational proof of the Noether normalization lemma Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pp.259-273, 1989.

A. Moitra, An almost optimal algorithm for computing nonnegative rank, SIAM Symposium on Discrete Algorithms, pp.1454-1464, 2012.

A. Neyman, Real Algebraic Tools in Stochastic Games, Stochastic Games and Applications, pp.57-75, 2003.
DOI : 10.1007/978-94-010-0189-2_6

M. Raghavan and B. Roth, Inverse Kinematics of the General 6R Manipulator and Related Linkages, Journal of Mechanical Design, vol.115, issue.3, p.502, 1993.
DOI : 10.1115/1.2919218

J. Renegar, On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, vol.13, issue.3, pp.255-299, 1992.
DOI : 10.1016/S0747-7171(10)80003-3

F. Rouillier, M. Roy, and M. , Finding at Least One Point in Each Connected Component of a Real Algebraic Set Defined by a Single Equation, Journal of Complexity, vol.16, issue.4, pp.716-750, 2000.
DOI : 10.1006/jcom.2000.0563
URL : https://hal.archives-ouvertes.fr/inria-00107845

M. Safey-el-din and E. Schost, A Baby Steps/Giant Steps Probabilistic Algorithm for??Computing Roadmaps in Smooth Bounded Real Hypersurface, Discrete & Computational Geometry, vol.43, issue.3, pp.181-220, 2011.
DOI : 10.1007/s00454-009-9239-2

J. T. Schwartz and M. Sharir, On the ???piano movers'??? problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers, Communications on Pure and Applied Mathematics, vol.22, issue.3, pp.345-398, 1983.
DOI : 10.1002/cpa.3160360305

J. T. Schwartz and M. Sharir, On the ???piano movers??? problem. II. General techniques for computing topological properties of real algebraic manifolds, Advances in Applied Mathematics, vol.4, issue.3, pp.298-351, 1983.
DOI : 10.1016/0196-8858(83)90014-3

I. Shafarevich, Basic Algebraic Geometry 1, 1977.
DOI : 10.1007/978-3-642-57908-0

J. Solymosi and T. Tao, An Incidence Theorem in Higher Dimensions, Discrete & Computational Geometry, vol.4, issue.2, pp.1-26, 2012.
DOI : 10.1007/s00454-012-9420-x

W. Szczechla, S. Connell, J. A. Filar, and O. Vrieze, On the Puiseux Series Expansion of the Limit Discount Equation of Stochastic Games, SIAM Journal on Control and Optimization, vol.35, issue.3, pp.860-875, 1997.
DOI : 10.1137/S0363012995284138

A. Tarski, A Decision Method for Elementary Algebra and Geometry, 1951.
DOI : 10.1007/978-3-7091-9459-1_3

N. Vorobjov, Complexity of Computing the Local Dimension of a Semialgebraic Set, Journal of Symbolic Computation, vol.27, issue.6, pp.565-579, 1999.
DOI : 10.1006/jsco.1999.0282