S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.
DOI : 10.1017/CBO9780511804090

L. Busé and C. , On the irreducibility of multivariate subresultants, Comptes Rendus Mathematique, vol.338, issue.4, pp.287-290, 2004.
DOI : 10.1016/j.crma.2003.12.019

J. F. Canny, A new algebraic method for robot motion planning and real geometry, 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp.39-48, 1987.
DOI : 10.1109/SFCS.1987.1

J. F. Canny, The complexity of robot motion planning, volume 1987 of ACM Doctoral Dissertation Award, 1988.

J. F. Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing , STOC '88, pp.460-469, 1988.
DOI : 10.1145/62212.62257

J. F. Canny, Generalized characteristic polynomials, Proc. ISSAC'88, 1989.
DOI : 10.1007/3-540-51084-2_28

J. F. Canny, E. Kaltofen, and L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation , ISSAC '89, pp.121-128, 1989.
DOI : 10.1145/74540.74556

J. F. Canny and J. H. Reif, New lower bound techniques for robot motion planning problems, 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp.49-60, 1987.
DOI : 10.1109/SFCS.1987.42

E. Cattani and A. Dickenstein, Introduction to residues and resultants, Solving polynomial equations, pp.1-61, 2005.
DOI : 10.1007/3-540-27357-3_1

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.8297

C. D. Andrea and A. Dickenstein, Explicit formulas for the multivariate resultant, Journal of Pure and Applied Algebra, vol.164, issue.1-2, pp.59-86, 2001.
DOI : 10.1016/S0022-4049(00)00145-6

A. Dixon, The Eliminant of Three Quantics in two Independent Variables, Proc. Lond, pp.468-478, 1908.
DOI : 10.1112/plms/s2-7.1.49

I. Emiris and B. Mourrain, Matrices in Elimination Theory, Journal of Symbolic Computation, vol.28, issue.1-2, pp.3-43, 1999.
DOI : 10.1006/jsco.1998.0266

N. Fitchas, A. Galligo, and J. Morgenstern, Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields, Journal of Pure and Applied Algebra, vol.67, issue.1, pp.1-14, 1990.
DOI : 10.1016/0022-4049(90)90159-F

H. Galperin and A. Wigderson, Succinct representations of graphs, Information and Control, vol.56, issue.3, pp.183-198, 1984.
DOI : 10.1016/S0019-9958(83)80004-7

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences. W. H. Freeman, 1979.

B. Grenet, Difficulté du résultant et des grands déterminants, pp.2009-2041, 2009.

D. Ierardi, Quantifier elimination in the theory of an algebraically-closed field, Proceedings of the twenty-first annual ACM symposium on Theory of computing , STOC '89, pp.138-147, 1989.
DOI : 10.1145/73007.73020

G. Jeronimo and J. Sabia, Computing multihomogeneous resultants using straight-line programs, Journal of Symbolic Computation, vol.42, issue.1-2, pp.218-235, 2007.
DOI : 10.1016/j.jsc.2006.03.006

E. Kaltofen and P. Koiran, On the complexity of factoring bivariate supersparse (Lacunary) polynomials, Proceedings of the 2005 international symposium on Symbolic and algebraic computation , ISSAC '05, pp.208-215, 2005.
DOI : 10.1145/1073884.1073914

E. Kaltofen and P. Koiran, Expressing a fraction of two determinants as a determinant, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, ISSAC '08, pp.141-146, 2008.
DOI : 10.1145/1390768.1390790

URL : https://hal.archives-ouvertes.fr/ensl-00232169

D. Kapur and T. Saxena, Comparison of various multivariate resultant formulations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation , ISSAC '95, pp.187-194, 1995.
DOI : 10.1145/220346.220370

D. Kapur, T. Saxena, and L. Yang, Algebraic and geometric reasoning using Dixon resultants, Proceedings of the international symposium on Symbolic and algebraic computation , ISSAC '94, pp.99-107, 1994.
DOI : 10.1145/190347.190372

P. Koiran, Hilbert's Nullstellensatz Is in the Polynomial Hierarchy, Journal of Complexity, vol.12, issue.4, pp.273-286, 1996.
DOI : 10.1006/jcom.1996.0019

P. Koiran, Circuits versus Trees in Algebraic Complexity, Proc. STACS'00, pp.35-54, 2000.
DOI : 10.1007/3-540-46541-3_3

P. Koiran, The Complexity of Local Dimensions for Constructible Sets, Journal of Complexity, vol.16, issue.1, pp.311-323, 2000.
DOI : 10.1006/jcom.1999.0536

T. Krick, L. Pardo, and M. Sombra, Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J, vol.109, issue.3, pp.521-598, 2001.

D. Lazard, Resolution des systemes d'equations algebriques, Theoretical Computer Science, vol.15, issue.1, pp.77-110, 1981.
DOI : 10.1016/0304-3975(81)90064-5

F. S. Macaulay, Some Formulae in Elimination, Proceedings of the London Mathematical Society, vol.1, issue.1, p.3, 1902.
DOI : 10.1112/plms/s1-35.1.3

F. S. Macaulay, The Algebraic Theory of Modular Systems. Cambridge Mathematical Library, 1994.

D. A. Plaisted, New NP-hard and NP-complete polynomial and integer divisibility problems, Theoretical Computer Science, vol.31, issue.1-2, pp.125-138, 1984.
DOI : 10.1016/0304-3975(84)90130-0

URL : http://dx.doi.org/10.1016/0304-3975(84)90130-0

J. Renegar, On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials, SIAM Journal on Computing, vol.18, issue.2, p.350, 1989.
DOI : 10.1137/0218024

A. Seidenberg, A New Decision Method for Elementary Algebra, The Annals of Mathematics, vol.60, issue.2, pp.365-374, 1954.
DOI : 10.2307/1969640

V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Mathematics of Computation, vol.54, issue.189, pp.435-447, 1990.
DOI : 10.1090/S0025-5718-1990-0993933-0

B. Sturmfels, Sparse elimination theory, Proc. Comput. Algebr. Geom. Commut. Algebra. D. Eisenbud and L. Robbiano, 1991.

B. L. Van-der-waerden, Modern Algebra, 1950.

J. Zur-gathen, M. Karpinski, and I. Shparlinski, Counting curves and their projections, computational complexity, vol.17, issue.1, pp.64-99, 1996.
DOI : 10.1007/BF01202042