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

J. Balcázar, The complexity of searching implicit graphs, Artificial Intelligence, vol.86, issue.1, pp.171-188, 1996.
DOI : 10.1016/0004-3702(96)00014-8

J. Balcázar, A. Lozano, and J. Torán, The Complexity of Algorithmic Problems on Succinct Instances, Computer Science : Research, pp.351-377, 1992.
DOI : 10.1007/978-1-4615-3422-8_30

S. Basu, R. Pollack, and M. Roy, Algorithms in Real Algebraic Geometry, 2003.
DOI : 10.1007/978-3-662-05355-3
URL : https://hal.archives-ouvertes.fr/hal-01083587

S. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, vol.18, issue.3, pp.147-150, 1984.
DOI : 10.1016/0020-0190(84)90018-8

L. Blum, M. Shub, F. Cucker, and S. Smale, Complexity and Real Computation, 1998.
DOI : 10.1007/978-1-4612-0701-6

L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: $NP$- completeness, recursive functions and universal machines, Bulletin of the American Mathematical Society, vol.21, issue.1, pp.1-46, 1989.
DOI : 10.1090/S0273-0979-1989-15750-9

A. Borodin, J. Zur-gathen, and J. Hopcroft, Fast parallel matrix and GCD computations, Information and Control, vol.52, issue.3, pp.241-256, 1982.
DOI : 10.1016/S0019-9958(82)90766-5

P. Bürgisser and F. Cucker, The complexity of semilinear problems in succinct representation, computational complexity, vol.15, issue.3, pp.197-235, 2006.
DOI : 10.1007/s00037-006-0213-6

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

A. Chandra and L. Stockmeyer, Constant Depth Reducibility, SIAM Journal on Computing, vol.13, issue.2, p.423, 1984.
DOI : 10.1137/0213028

Q. Cheng, S. P. Tarasov, and M. N. , Vyalyi : Efficient algorithms for sparse cyclotomic integer zero testing, Theory of Comput. Syst, 2009.

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

G. Collins, The calculation of multivariate polynomial resultants, Proc. 2nd ACM Symp. on Symbolic and Algebraic Manipulation, pp.212-222, 1971.

M. Crasmaru, PSPACE problems with unique solutions, IEIC Technical Report, vol.100, issue.705, pp.129-136, 2001.

L. Csanky, Fast Parallel Matrix Inversion Algorithms, SIAM Journal on Computing, vol.5, issue.4, p.618, 1976.
DOI : 10.1137/0205040

C. D. Andrea, 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, Proceedings of the London Mathematical Society, vol.2, issue.1, pp.468-478, 1908.
DOI : 10.1112/plms/s2-7.1.49

J. Feigenbaum, S. Kannan, M. Vardi, and M. Viswanathan, Complexity of problems on graphs represented as OBDDs (extended abstract), Proc. STACS'98, p.216, 1998.

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

S. P. Jordan and P. J. Love, QMA-complete problems for stoquastic Hamiltonians and Markov matrices, 2009.

S. P. Jordan, Wocjan : Efficient quantum circuits for arbitrary sparse unitaries, 2009.

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

P. Koiran and S. Perifel, VPSPACE and a Transfer Theorem over the Complex Field, Proc. MFCS'07, pp.359-370, 2007.
DOI : 10.1007/978-3-540-74456-6_33
URL : https://hal.archives-ouvertes.fr/ensl-00153701

P. Koiran and N. Portier, A rank theorem for Vandermonde matrices, Linear Algebra and its Applications, vol.378, pp.99-108, 2004.
DOI : 10.1016/j.laa.2003.09.007

J. Kollár, Sharp Effective Nullstellensatz, Journal of the American Mathematical Society, vol.1, issue.4, pp.963-975, 1988.
DOI : 10.2307/1990996

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

A. Lozano and J. Balcázar, The complexity of graph problems for succinctly represented graphs, Proc. 15th Int. Workshop WG'89, p.277, 1990.
DOI : 10.1007/3-540-52292-1_20

F. 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

K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, vol.11, issue.1, pp.101-104, 1987.
DOI : 10.1007/BF02579205

C. Papadimitriou, Computational complexity, 1994.

C. Papadimitriou, A note on succinct representations of graphs, Information and Control, vol.71, issue.3, pp.181-185, 1986.
DOI : 10.1016/S0019-9958(86)80009-2

B. Sturmfels, Sparse elimination theory, Proc. Computat. Algebraic Geom. and Commut. Algebra. D. Eusenbud and L. Robbiano, 1991.

J. Torán, Succinct representations of counting problems, Proc. 6th Int. Conf. Appl. Algebra, Algebraic Algo. and Error-Correcting Codes, pp.415-426, 1988.
DOI : 10.1007/3-540-51083-4_77

K. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, vol.3, issue.3, pp.325-356, 1986.
DOI : 10.1007/BF00289117

B. Grenet and L. Lyon, 46 allée d'Italie, 69364 Lyon Cedex 07, France Courriel : Bruno.Grenet@ens-lyon.fr ? Url