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.

C. Bajaj, Some Applications of Constructive Real Algebraic Geometry, 1994.
DOI : 10.1007/978-1-4612-2628-4_25

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. 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, A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials, Quantifier elimination and cylindrical algebraic decomposition, 1998.
DOI : 10.1007/978-3-7091-9459-1_17

S. Basu, R. Pollack, and M. Roy, Computing roadmaps of semialgebraic sets on a variety, Journal of the AMS, vol.3, issue.1, pp.55-82, 1999.

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, M. Roy, and M. , Safey El Din, and E. Schost. A baby-step giant-step roadmap algorithm for general real algebraic sets, 2012.

V. D. Blondel, Simultaneous stabilization of linear systems and interpolation with rational functions. In Open problems in mathematical systems and control theory, pp.53-59, 1999.

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

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

J. Faugère, M. Safey-el-din, and P. Spaenlehauer, Gr??bner bases of bihomogeneous ideals generated by polynomials of bidegree <mml:math altimg="si1.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math>: Algorithms and complexity, Journal of Symbolic Computation, vol.46, issue.4, pp.406-437, 2011.
DOI : 10.1016/j.jsc.2010.10.014

J. Faugère, M. Safey-el-din, and P. Spaenlehauer, Critical points and Gröbner bases: the unmixed case, pp.162-169, 2012.

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

M. Giusti, G. Lecerf, and B. Salvy, A Gr??bner Free Alternative for Polynomial System Solving, Journal of Complexity, vol.17, issue.1, pp.154-211, 2001.
DOI : 10.1006/jcom.2000.0571

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

G. Jeronimo, D. Perrucci, and J. Sabia, On Sign Conditions Over Real Multivariate Polynomials, Discrete & Computational Geometry, vol.60, issue.5, pp.195-222, 2010.
DOI : 10.1007/s00454-009-9200-4

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

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

M. Safey-el-din, Testing Sign Conditions on a Multivariate Polynomial and Applications, Mathematics in Computer Science, vol.1, issue.1, pp.177-207, 2007.
DOI : 10.1007/s11786-007-0003-9
URL : https://hal.archives-ouvertes.fr/inria-00105835

M. Safey-el-din and E. Schost, Polar varieties and computation of one point in each connected component of a smooth real algebraic set, Proceedings of the 2003 international symposium on Symbolic and algebraic computation , ISSAC '03, pp.224-231, 2003.
DOI : 10.1145/860854.860901
URL : https://hal.archives-ouvertes.fr/inria-00099649

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

M. Safey-el-din and E. Tsigaridas, A probabilistic algorithm to compute the real dimension of a semi-algebraic set. ArXiv e-prints 1304, 1928.
URL : https://hal.archives-ouvertes.fr/hal-00808708

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

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