S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.

N. Amini and P. Brändén, Non-representable hyperbolic matroids, Adv. Math, vol.334, pp.417-449, 2018.
URL : https://hal.archives-ouvertes.fr/hal-02173792

X. Allamigeon, P. Benchimol, and S. Gaubert, The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average, Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), vol.8572, pp.89-100, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01096447

X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig, Combinatorial simplex algorithms can solve mean payoff games, SIAM J. Optim, vol.24, issue.4, pp.2096-2117, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01097727

X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig, Tropicalizing the simplex algorithm, SIAM J. Discrete Math, vol.29, issue.2, pp.751-795, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00930959

X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig, Log-barrier interior point methods are not strongly polynomial, SIAM J. Appl. Algebra Geom, vol.2, issue.1, pp.140-178, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01674959

E. Allender, P. Bürgisser, J. Kjeldgaard-pedersen, and P. B. Miltersen, On the complexity of numerical analysis, SIAM J. Comput, vol.38, issue.5, 1987.

]. E. Acd-+-16, J. Asarin, A. Cervelle, C. Degorre, F. Dima et al., Entropy games and matrix multiplication games, Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS), vol.11, pp.1-11, 2016.

P. Ashok, K. Chatterjee, P. Daca, J. K?etínský, and T. Meggendorfer, Value iteration for long-run average reward in Markov decision processes, Proceedings of Bibliography the 29th International Conference on Computer-Aided Verification (CAV), vol.10426, pp.201-221, 2017.

D. Auger, P. Coucheney, and Y. Strozecki, Finding optimal strategies of almost acyclic simple stochastic games, Proceedings of the 11th Annual Conference on Theory and Applications of Models of Computation (TAMC), vol.8402, pp.67-85, 2014.

M. Akian, J. Cochet-terrasson, S. Detournay, and S. Gaubert, Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00773080

M. Akian, S. Gaubert, and A. Guterman, Linear independence over tropical semirings and beyond, Proceedings of the International Conference on Tropical and Idempotent Mathematics, vol.495, pp.1-38, 2009.

M. Akian, S. Gaubert, and A. Guterman, Tropical polyhedra are equivalent to mean payoff games, Int. J. Algebra Comput, vol.22, issue.1, p.125001, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00778078

M. Akian, S. Gaubert, J. Grand-clément, and J. Guillaud, The operator approach to entropy games, Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), vol.66, pp.1-6, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01676695

M. Akian, S. Gaubert, and A. Hochart, Ergodicity conditions for zero-sum games, Discrete Contin. Dyn. Syst, vol.35, issue.9, pp.3901-3931, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01096206

M. Akian, S. Gaubert, and A. Hochart, Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information, J. Math. Anal. Appl, vol.457, pp.1038-1064, 2018.

X. Allamigeon, S. Gaubert, and R. D. Katz, The number of extreme points of tropical polyhedra, J. Combin. Theory Ser. A, vol.118, issue.1, pp.162-189, 2011.

X. Allamigeon, S. Gaubert, M. Skomra, and . Solvenonarchsdp, A solver for tropically generic Metzler nonarchimedean semidefinite feasibility problems, 2016.

X. Allamigeon, S. Gaubert, and M. Skomra, Tropical spectrahedra, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01676701

X. Allamigeon, S. Gaubert, and M. Skomra, Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, J. Symb. Comp, vol.85, pp.25-54, 2018.
DOI : 10.1145/2930889.2930935
URL : https://hal.archives-ouvertes.fr/hal-01676704

X. Allamigeon, S. Gaubert, and M. Skomra, The tropical analogue of the HeltonNie conjecture is true, J. Symbolic Comput, vol.91, pp.129-148, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01674497

X. Allamigeon and R. D. Katz, Tropicalization of facets of polytopes, Linear Algebra Appl, vol.523, pp.79-101, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01096435

M. F. Anjos and J. B. Lasserre, Handbook on Semidefinite, Conic and Polynomial Optimization, vol.166, 2012.

D. Alessandrini, Logarithmic limit sets of real semi-algebraic sets, Adv. Geom, vol.13, issue.1, pp.155-190, 2013.

F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim, vol.5, issue.1, pp.13-51, 1995.

D. Andersson and P. B. Miltersen, The complexity of solving stochastic games on graphs, Proceedings of the 20th International Symposium on Algorithms and Computation, vol.5878, pp.112-121, 2009.

W. A. Adkins and S. H. Weintraub, Algebra. An Approach via Module Theory, Grad. Texts in Math, vol.136, 1992.

M. Baker and N. Bowler, Matroids over hyperfields, 2016.
DOI : 10.1063/1.5043953
URL : http://arxiv.org/pdf/1601.01204

F. Baccelli, G. Cohen, G. J. Olsder, and J. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems, 1992.

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

S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM Stud. Appl. Math. SIAM, vol.15, 1994.

E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness, Oper. Res. Lett, vol.41, issue.4, pp.357-362, 2013.

E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, 2015.

E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, A convex programming-based algorithm for mean payoff stochastic games with perfect information, Optim. Lett, vol.11, issue.8, pp.1499-1512, 2017.

G. M. Bergman, The logarithmic limit-set of an algebraic variety, Trans. Amer. Math. Soc, vol.157, pp.459-469, 1971.

R. Bieri and J. R. Groves, The geometry of the set of characters induced by valuations, J. Reine Angew. Math, vol.347, pp.168-195, 1984.

W. Briec and C. Horvath, , vol.53, pp.103-127, 2004.

F. Bihan, Viro method for the construction of real complete intersections, Adv. Math, vol.169, issue.2, pp.177-186, 2002.

T. Bewley and E. Kohlberg, The asymptotic theory of stochastic games, Math. Oper. Res, vol.1, issue.3, pp.197-208, 1976.
DOI : 10.1287/moor.1.3.197

E. Brieskorn and H. Knörrer, Plane Algebraic Curves, 2012.

M. Bodirsky and M. Mamino, Max-closed semilinear constraint satisfaction, Proceedings of the 11th International Computer Science Symposium in Russia (CSR), vol.9691, pp.88-101, 2016.
DOI : 10.1007/978-3-319-34171-2_7

A. D. Burbanks, R. D. Nussbaum, and C. T. Sparrow, Extension of orderpreserving maps on a cone, Proc. Roy. Soc. Edinburgh Sect. A, vol.133, issue.1, pp.35-59, 2003.
DOI : 10.1017/s0308210500002274

N. Bourbaki, Algebra II, 2003.

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

G. Blekherman, P. A. Parrilo, and R. R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Ser. Optim. SIAM, vol.13, 2013.

P. Brändén, Obstructions to determinantal representability, Adv. Math, vol.226, issue.2, pp.1202-1212, 2011.

A. Browder, Mathematical Analysis. An Introduction. Undergrad. Texts Math, 1996.

A. Berman and N. Shaked-monderer, Completely Positive Matrices. World Scientific Publishing, 2003.

L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: N P-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc, vol.21, pp.1-46, 1989.

P. Butkovi?, H. Schneider, and S. Sergeev, Generators, extremals and bases of max cones, Linear Algebra Appl, vol.421, issue.2-3, pp.394-406, 2007.

H. Björklund, S. Sandberg, and S. Vorobyov, A discrete subexponential algorithm for parity games, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol.2607, pp.663-674, 2003.

A. Ben-tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol.2, 2001.

P. Butkovi?, Max-linear Systems: Theory and Algorithms, 2010.

S. Boyd and L. Vandenberghe, Covex Optimization, 2004.

H. Björklund and S. Vorobyov, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, Discrete Appl. Math, vol.155, issue.2, pp.210-229, 2007.

S. Burton, C. Vinzant, and Y. Youm, A real stable extension of the Vámos matroid polynomial, 2014.

H. Cartan, Sur le théorème de préparation de Weierstraß, Festschrift zur Gedächtnisfeier für Karl Weierstraß 18151965, pp.155-168, 1966.

O. Catoni, Simulated annealing algorithms and Markov chains with rare transitions, Séminaire de Probabilités XXXIII, vol.1709, pp.69-119, 1999.

A. Connes and C. Consani, The hyperring of adèle classes, J. Number Theory, vol.131, issue.2, pp.159-194, 2011.

K. Chatterjee and L. Doyen, Energy parity games, Theoret. Comput. Sci, vol.458, pp.49-60, 2012.
DOI : 10.1007/978-3-642-14162-1_50

W. Czerwi?ski, L. Daviaud, N. Fijalkow, M. Jurdzi?ski, R. Lazi? et al., Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games, 2018.

K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, Perfect-information stochastic mean-payoff parity games, Proceedings of the 17th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS), vol.8412, pp.210-225, 2014.
DOI : 10.1007/978-3-642-54830-7_14
URL : https://hal.archives-ouvertes.fr/hal-01006391

G. Cohen, S. Gaubert, and J. Quadrat, Duality and separation theorems in idempotent semimodules, Linear Algebra Appl, vol.379, pp.395-422, 2004.
DOI : 10.1016/j.laa.2003.08.010
URL : https://hal.archives-ouvertes.fr/inria-00071917

G. Cohen, S. Gaubert, J. Quadrat, and I. Singer, Max-plus convex sets and functions, Idempotent Mathematics and Mathematical Physics, vol.377, pp.105-129, 2005.
DOI : 10.1090/conm/377/06987
URL : http://arxiv.org/pdf/math/0308166

K. L. Chung, Markov Chains With Stationary Transition Probabilities, Grundlehren Math. Wiss. Springer, vol.104, 1967.

K. Chatterjee and R. Ibsen-jensen, The complexity of ergodic mean-payoff games, Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), vol.8573, pp.122-133, 2014.

K. Chatterjee, M. Jurdzi?ski, and T. A. Henzinger, Quantitative stochastic parity games, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.121-130, 2004.
DOI : 10.1007/978-3-540-45220-1_11

C. S. Calude, S. Jain, B. Khoussainov, W. Li, and F. Stephan, Deciding parity games in quasipolynomial time, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp.252-263, 2017.
DOI : 10.1145/3055399.3055409

R. Cluckers, L. Lipshitz, and Z. Robinson, Analytic cell decomposition and analytic motivic integration, Ann. Sci. Éc. Norm. Supér, vol.39, issue.4, pp.535-568, 2006.

A. Condon, The complexity of stochastic games, Inform. and Comput, vol.96, issue.2, pp.203-224, 1992.

C. Comin and R. Rizzi, Improved pseudo-polynomial bound for the value problems and optimal strategy synthesis in mean payoff games, Algorithmica, vol.77, issue.4, pp.995-1021, 2017.

M. G. Crandall and L. Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc, vol.78, issue.3, pp.385-390, 1980.
DOI : 10.2307/2042330
URL : https://www.ams.org/proc/1980-078-03/S0002-9939-1980-0553381-X/S0002-9939-1980-0553381-X.pdf

J. Denef, The rationality of the Poincaré series associated to the p-adic points on a variety, Invent. Math, vol.77, pp.1-23, 1984.

J. Denef, p-adic semi-algebraic sets and cell decomposition, J. Reine Angew. Math, vol.369, pp.154-166, 1986.

Y. Disser and A. V. Hopp, On Friedmann's subexponential lower bound for Zadeh's pivot rule, 2017.
DOI : 10.1007/978-3-030-17953-3_13
URL : http://tuprints.ulb.tu-darmstadt.de/6873/1/On%20Friedmann%27s%20subexponential%20lower%20bound%20for%20Zadeh%27s%20pivot%20rule.pdf

A. Degtyarev and I. Itenberg, On real determinantal quartics, Proceedings of Gökova Geometry-Topology Conference 2010, pp.110-128, 2010.

L. Daviaud, M. Jurdzi?ski, and R. Lazi?, A pseudo-quasi-polynomial algorithm for mean-payoff parity games, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp.325-334, 2018.
DOI : 10.1145/3209108.3209162
URL : http://wrap.warwick.ac.uk/101797/1/WRAP-pseudo-quasi-polynomial-algorithm-Daviaud-2018%2520%25281%2529.pdf

E. De-klerk, Aspects of Semidefinite Programming. Interior Point Algorithms and Selected Applications, Appl. Optim, vol.65, 2002.

E. De-klerk and F. Vallentin, On the Turing model complexity of interior point methods for semidefinite programming, SIAM J. Optim, vol.26, issue.3, pp.1944-1961, 2016.

C. Daskalakis and C. Papadimitriou, Continuous local search, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.790-804, 2011.
DOI : 10.1137/1.9781611973082.62

M. Develin and B. , Sturmfels. Tropical convexity. Doc. Math, vol.9, pp.1-27, 2004.

M. Develin and J. Yu, Tropical polytopes and cellular resolutions, Exp. Math, vol.16, issue.3, pp.277-291, 2007.
DOI : 10.1080/10586458.2007.10129009
URL : http://arxiv.org/pdf/math/0605494v2.pdf

J. Edmonds, Optimum branchings, J. Res. Bur. Stand, vol.71, issue.4, pp.233-240, 1967.
DOI : 10.6028/jres.071b.032
URL : https://doi.org/10.6028/jres.071b.032

D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Grad. Texts in Math, vol.150, 2004.

E. A. Emerson and C. S. Jutla, Tree automata, mu-calculus and determinacy, Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS), pp.368-377, 1991.
DOI : 10.1109/sfcs.1991.185392

E. A. Emerson, C. S. Jutla, and A. P. Sistla, On model-checking fragments of µcalculus, Proceedings of the 5th International Conference on Computer-Aided Verification (CAV), vol.697, pp.385-396

. Springer, , 1993.

M. Einsiedler, M. Kapranov, and D. Lind, Non-archimedean amoebas and tropical varieties, J. Reine Angew. Math, vol.601, pp.139-157, 2006.
DOI : 10.1515/crelle.2006.097
URL : http://arxiv.org/pdf/math/0408311v1.pdf

A. Ehrenfeucht and J. Mycielski, Positional strategies for mean payoff games, Internat. J. Game Theory, vol.8, issue.2, pp.109-113, 1979.
DOI : 10.1007/bf01768705

H. B. Enderton, A Mathematical Introduction to Logic, 2001.

A. J. Engler and A. Prestel, Valued Fields, 2005.

B. C. Eaves and U. G. Rothblum, Dines-Fourier-Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields, Math. Program, vol.53, issue.1-3, pp.307-321, 1992.

K. Etessami and M. Yannakakis, On the complexity of Nash equilibria and other fixed points, SIAM J. Comput, vol.39, issue.6, pp.2531-2597, 2010.

J. Fearnley, Exponential lower bounds for policy iteration, Proceedings of the 37th International Colloquium on Automata, Languages, and Programming (ICALP), vol.6199, pp.551-562, 2010.

O. Friedmann, T. D. Hansen, and U. Zwick, Random-Facet and Random-Bland require subexponential time even for shortest paths, 2014.

J. Fearnley, S. Jain, S. Schewe, F. Stephan, and D. Wojtczak, An ordered approach to solving parity games in quasi polynomial time and quasi linear space, Proceedings of the 24th ACM SIGSOFT International Symposium on Model Checking of Software (SPIN), pp.112-121, 2017.

M. Fori?ek, Approximating rational numbers by fractions, Proceedings of the 4th International Conference on Fun with Algorithms (FUN), vol.4475, pp.156-165, 2007.

J. Ferrante and C. Rackoff, A decision procedure for the first order theory of real addition with order, SIAM J. Comput, vol.4, issue.1, pp.69-76, 1975.

O. Friedmann, A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games, Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization, vol.6655, pp.192-206, 2011.
DOI : 10.1007/978-3-642-20807-2_16

H. Fawzi and M. Safey-el-din, A lower bound on the positive semidefinite rank of convex bodies, SIAM J. Appl. Algebra Geom, vol.2, issue.1, pp.126-139, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01657849

H. Fawzi, J. Saunderson, and P. A. Parrilo, Semidefinite approximations of the matrix logarithm, Found. Comput. Math, 2018.

M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Grundlehren Math. Wiss. Springer, vol.260, 2012.

S. Gribling, D. De-laat, and M. Laurent, Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization, Math. Program, vol.170, issue.1, pp.5-42, 2018.

S. Gaubert and J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc, vol.356, issue.12, pp.4931-4950, 2004.

M. R. Garey, R. L. Graham, and D. S. Johnson, Some NP-complete geometric problems, Proceedings of the 8th Annual ACM Symposium on Theory of Computing (STOC), pp.10-22, 1976.
DOI : 10.1145/800113.803626
URL : http://www.cs.ust.hk/mjg_lib/bibs/qzhang_lib/NP-hardness/10 - 22.pdf

H. Gimbert and F. Horn, Simple stochastic games with few random vertices are easy to solve, Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS), vol.4962, pp.5-19, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00343656

H. Gimbert and R. Ibsen-jensen, A short proof of correctness of the quasipolynomial time algorithm for parity games, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01457996

D. Gillette, Stochastic games with zero stop probabilities, Contributions to the Theory of Games III, vol.39, pp.179-188, 1957.

S. Gaubert and R. D. Katz, The Minkowski theorem for max-plus convex sets, Linear Algebra Appl, vol.421, issue.2-3, pp.356-369, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00071358

V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan, Cyclic games and finding minimax mean cycles in digraphs, Zh. Vychisl. Mat. Mat. Fiz, vol.28, issue.9, pp.1406-1417, 1988.

M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms Combin, vol.2, 1993.

B. Gärtner and J. Matou?ek, Approximation Algorithms and Semidefinite Programming, 2012.

J. Gouveia and T. Netzer, Positive polynomials and projections of spectrahedra, SIAM J. Optim, vol.21, issue.3, pp.960-976, 2011.

D. Grigoriev and V. V. Podolskii, Complexity of tropical and min-plus linear prevarieties, comput. complexity, vol.24, issue.1, pp.31-64, 2015.

J. Gouveia, P. A. Parrilo, and R. R. Thomas, Theta bodies for polynomial ideals, SIAM J. Optim, vol.20, issue.4, pp.2097-2118, 2010.
DOI : 10.1137/090746525
URL : http://arxiv.org/pdf/0809.3480

B. Grünbaum, Convex Polytopes, Grad. Texts in Math, vol.221, 2003.

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Maximum Cut and Satisfiability problems using semidefinite programming, J. ACM, vol.42, issue.6, pp.1115-1145, 1995.
DOI : 10.1145/227683.227684

N. Halman, Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems, Algorithmica, vol.49, issue.1, pp.37-50, 2007.
DOI : 10.1007/s00453-007-0175-3

S. Helbig, On Carathéodory's and Kre? ?n-Milman's theorems in fully ordered groups, Comment. Math. Univ. Carolin, vol.29, issue.1, pp.157-167, 1988.

A. J. Hoffman and R. M. Karp, On nonterminating stochastic games, Manag. Sci, vol.12, issue.5, pp.359-370, 1966.

T. D. Hansen, P. B. Miltersen, and U. Zwick, Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor, J. ACM, vol.60, pp.1-16, 2013.

J. W. Helton and J. Nie, Sufficient and necessary conditions for semidefinite representability of convex hulls and sets, SIAM J. Optim, vol.20, issue.2, pp.759-791, 2009.

J. W. Helton and J. Nie, Semidefinite representation of convex sets, Math. Program, vol.122, issue.1, pp.21-64, 2010.

D. Henrion, S. Naldi, and M. Safey-el-din, Exact algorithms for linear matrix inequalities, SIAM J. Optim, vol.26, issue.4, pp.2512-2539, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01184320

D. Henrion, S. Naldi, and M. Safey-el-din, Exact algorithms for semidefinite programs with degenerate feasible set, Proceedings of the 43rd International Symposium on Symbolic and Algebraic Computation (ISSAC), pp.191-198, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01705590

G. H. Hardy and M. Riesz, The general theory of Dirichlet's series, 1915.

J. W. Helton and V. Vinnikov, Linear matrix inequality representation of sets, Comm. Pure Appl. Math, vol.60, issue.5, pp.654-674, 2007.

T. D. Hansen and U. Zwick, An improved version of the Random-Facet pivoting rule for the simplex algorithm, Proceedings of the 47th Annual ACM Symposium on the Theory of Computing (STOC), pp.209-218, 2015.

R. Ibsen-jensen and P. B. Miltersen, Solving simple stochastic games with few coin toss positions, Proceedings of the 20th Annual European Symposium on Algorithms (ESA), vol.7501, pp.636-647

. Springer, , 2012.

I. Itenberg, G. Mikhalkin, and E. Shustin, Tropical algebraic geometry, Oberwolfach Semin. Birkhäuser, vol.35, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00143239

I. Itenberg and O. Viro, Patchworking algebraic curves disproves the Ragsdale conjecture, Math. Intelligencer, vol.18, issue.4, pp.19-28, 1996.

M. Jurdzi?ski and R. Lazi?, Succinct progress measures for solving parity games, Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), vol.9, 2017.

C. Josz and D. K. Molzahn, Lasserre hierarchy for large scale polynomial optimization in real and complex variables, SIAM J. Optim, vol.28, issue.2, pp.1017-1048, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01592093

A. Jensen, H. Markwig, and T. Markwig, An algorithm for lifting points in a tropical variety, Collect. Math, vol.59, issue.2, pp.129-165, 2008.

M. Joswig, Tropical half-spaces, Combinatorial and Computational Geometry, vol.52, pp.409-431, 2005.

M. Jurdzi?ski, M. Paterson, and U. Zwick, A deterministic subexponential algorithm for solving parity games, SIAM J. Comput, vol.38, issue.4, pp.1519-1532, 2008.

P. Jonsson and J. Thapper, Tractability conditions for numeric CSPs, Theoret. Comput. Sci, vol.715, pp.21-34, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01796723

M. Jurdzi?ski, Deciding the winner in parity games is in UP ? co-UP, Inform. Process. Lett, vol.68, issue.3, pp.119-124, 1998.

R. M. Karp, A simple derivation of Edmonds' algorithm for optimum branchings, Networks, vol.1, issue.3, pp.265-272, 1971.

S. Kwek and K. Mehlhorn, Optimal search for rationals, Inform. Process. Lett, vol.86, issue.1, pp.23-26, 2003.
DOI : 10.1016/s0020-0190(02)00455-6

E. Kohlberg, Invariant half-lines of nonexpansive piecewise-linear transformations, Math. Oper. Res, vol.5, issue.3, pp.366-372, 1980.

V. N. Kolokoltsov, On linear, additive, and homogeneous operators in idempotent analysis, Adv. Soviet Math, vol.13, pp.87-101, 1992.

K. Kellner, M. P. Pfetsch, and T. Theobald, Irreducible infeasible subsystems of semidefinite systems, 2018.

J. G. Kemeny and J. L. Snell, Finite Markov Chains. Undergrad. Texts Math, 1976.

I. Klep and M. Schweighofer, An exact duality theory for semidefinite programming based on sums of squares, Math. Oper. Res, vol.38, issue.3, pp.569-590, 2013.

K. Kellner, T. Theobald, and C. Trabandt, Containment problems for polytopes and spectrahedra, SIAM J. Optim, vol.23, issue.2, pp.1000-1020, 2013.
DOI : 10.1137/120874898
URL : http://arxiv.org/pdf/1204.4313

M. Kummer, Determinantal representations and Bézoutians, Math. Z, vol.285, issue.12, pp.445-459, 2017.
DOI : 10.1007/s00209-016-1715-9
URL : http://arxiv.org/pdf/1308.5560

J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim, vol.11, issue.3, pp.796-817, 2001.

J. B. Lasserre, An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM J. Optim, vol.12, issue.3, pp.756-769, 2002.

J. B. Lasserre, Convex sets with semidefinite representation, Math. Program, vol.120, issue.2, pp.457-477, 2009.
DOI : 10.1007/s10107-008-0222-0
URL : https://hal.archives-ouvertes.fr/hal-00331665

J. B. Lasserre, Moments, Positive Polynomials and Their Applications. Ser. Optim, 2009.
DOI : 10.1142/p665

J. B. Lasserre, An Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge Texts Appl. Math, 2015.
DOI : 10.1017/cbo9781107447226
URL : https://hal.archives-ouvertes.fr/hal-02095856

M. Laurent, Polynomial instances of the positive semidefinite and euclidean distance matrix completion problems, SIAM J. Matrix Anal. Appl, vol.22, issue.3, pp.874-894, 2001.

M. K. Lehtinen, A modal µ perspective on solving parity games in quasipolynomial time, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp.639-648, 2018.

T. M. Liggett and S. A. Lippman, Stochastic games with perfect information and time average payoff, SIAM Rev, vol.11, issue.4, pp.604-607, 1969.
DOI : 10.1137/1011093

G. L. Litvinov, V. P. Maslov, and G. B. Shpiz, Idempotent functional analysis: An algebraic approach, Mathematical Notes, vol.69, issue.5-6, pp.696-729, 2001.
DOI : 10.1007/bf02675362
URL : http://arxiv.org/pdf/math/0101153

B. F. Lourenço, M. Muramatsu, and T. Tsuchiya, Solving SDP completely with an interior point oracle, 2015.

L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, vol.25, pp.1-7, 1979.

M. Liu and G. Pataki, Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming, Math. Program, vol.167, issue.2, pp.435-480, 2018.

A. S. Lewis, P. A. Parrilo, and M. V. Ramana, The Lax conjecture is true, Proc. Amer. Math. Soc, vol.133, issue.9, pp.2495-2499, 2005.

M. Laurent and F. Rendl, Semidefinite programming and integer programming, Discrete Optimization, vol.12, pp.393-514, 2005.

R. Laraki and S. Sorin, Advances in zero-sum dynamic games, Handbook of Game Theory with Economic Applications, vol.4, pp.27-93, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01098241

W. Ludwig, A subexponential randomized algorithm for the simple stochastic game problem, Inform. and Comput, vol.117, issue.1, pp.151-155, 1995.

M. Laurent and A. Varvitsiotis, Positive semidefinite matrix completion, universal rigidity and the Strong Arnold Property, Linear Algebra Appl, vol.452, pp.292-317, 2014.

R. Loos and V. Weispfenning, Applying linear quantifier elimination, Comput. J, vol.36, issue.5, pp.450-462, 1993.

V. Magron, X. Allamigeon, S. Gaubert, and B. Werner, Certification of real inequalities: templates and sums of squares, Math. Program, vol.151, issue.2, pp.477-506, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01096485

M. Mamino, Strategy recovery for stochastic mean payoff games, Theoret. Comput. Sci, vol.675, pp.101-104, 2017.

D. Marker, Model Theory: An Introduction, Grad. Texts in Math, vol.217, 2002.

T. Markwig, A field of generalized Puiseux series for tropical geometry, Rend. Sem. Mat. Univ. Politec. Torino, vol.68, issue.1, pp.79-92, 2010.

D. Monniaux and P. Corbineau, On the generation of Positivstellensatz witnesses in degenerate cases, Proceedings of the 2nd International Conference on Interactive Theorem Proving (ITP), pp.249-264, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00594761

N. Megiddo, On the complexity of linear programming, Advances in economic theory, vol.12, pp.225-268

C. D. Meyer, Matrix Analysis and Applied Linear Algebra, 2000.

G. Mikhalkin, Enumerative tropical algebraic geometry in R 2, J. Amer. Math. Soc, vol.18, pp.313-377, 2005.

J. Mertens and A. Neyman, Stochastic games, Internat. J. Game Theory, vol.10, issue.2, pp.53-66, 1981.

A. W. Mostowski, Games with forbidden positions, 1991.

D. Maclagan and B. Sturmfels, Introduction to Tropical Geometry, Grad. Stud. Math. AMS, vol.161, 2015.

J. Matou?ek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, Algorithmica, vol.16, issue.4-5, pp.498-516, 1996.

J. Mertens, S. Sorin, and S. Zamir, Repeated games, Econom. Soc. Monogr, vol.55, 2015.

S. Naldi, Solving rank-constrained semidefinite programs in exact arithmetic, J. Symbolic Comput, vol.85, pp.206-223, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01363339

A. Nemirovski, Advances in convex optimization: conic programming, Proceedings of the International Congress of Mathematicians (ICM) 2006, volume I, pp.413-444, 2007.

A. Neyman, Stochastic games and nonexpansive maps, Stochastic Games and Applications, vol.570, pp.397-415, 2003.

Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming, Studies in Applied and Numerical Mathematics. SIAM, vol.13, 1994.

J. Nie, P. Parrilo, and B. Sturmfels, Semidefinite representation of the k-ellipse, Algorithms in Algebraic Geometry, vol.146, pp.117-132, 2008.

J. Nie, K. Ranestad, and B. Sturmfels, The algebraic degree of semidefinite programming, Math. Program, vol.122, issue.2, pp.379-405, 2010.

T. Netzer and R. Sinn, A note on the convex hull of finitely many projections of spectrahedra, 2009.

R. D. Nussbaum, Convexity and log convexity for the spectral radius, Linear Algebra Appl, vol.73, pp.59-122, 1986.

J. C. Ottem, K. Ranestad, B. Sturmfels, and C. Vinzant, Quartic spectrahedra, Math. Program, vol.151, issue.2, pp.585-612, 2015.

S. Ovchinnikov, Max-min representations of piecewise linear functions, Beitr. Algebra Geom, vol.43, issue.1, pp.297-302, 2002.

C. H. Papadimitriou, The Euclidean travelling salesman problem is NP-complete

, Theoret. Comput. Sci, vol.4, issue.3, pp.237-244, 1977.

P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program, vol.96, issue.2, pp.293-320, 2003.

J. Pas, Uniform p-adic cell decomposition and local zeta functions, J. Reine Angew. Math, vol.399, pp.137-172, 1989.

J. Pas, Cell decomposition and local zeta functions in a tower of unramified extensions of a p-adic field, Proc. London Math. Soc, vol.60, issue.3, pp.37-67, 1990.

J. Pas, On the angular component map modulo P, J. Symb. Log, vol.55, issue.3, pp.1125-1129, 1990.

D. P. Palomar and Y. C. Eldar, Convex Optimization in Signal Processing and Communications, 2010.

L. Porkolab and L. Khachiyan, On the complexity of semidefinite programs, J. Global Optim, vol.10, issue.4, pp.351-365, 1997.

M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, 2005.

D. Plaumann and C. Vinzant, Determinantal representations of hyperbolic plane curves: an elementary approach, J. Symbolic Comput, vol.57, pp.48-60, 2013.

M. V. Ramana, An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems, 1993.

M. V. Ramana, An exact duality theory for semidefinite programming and its complexity implications, Math. Program, vol.77, issue.1, pp.129-162, 1997.

J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, MOS-SIAM Ser. Optim. SIAM, vol.3, 2001.

J. Renegar, Hyperbolic programs, and their derivative relaxations, Found. Comput. Math, vol.6, issue.1, pp.59-79, 2006.
DOI : 10.1007/s10208-004-0136-z
URL : https://ecommons.cornell.edu/bitstream/1813/9281/1/TR001406.pdf

M. Ramana and A. J. Goldman, Some geometric results in semidefinite programming, J. Global Optim, vol.7, issue.1, pp.33-50, 1995.

J. Richter-gebert, B. Sturmfels, and T. Theobald, First steps in tropical geometry, Idempotent Mathematics and Mathematical Physics, vol.377, pp.289-317, 2005.

D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games

J. Israel and . Math, , vol.121, pp.221-246, 2001.

P. Roux, Y. Voronin, and S. Sankaranarayanan, Validating numerical semidefinite programming solvers for polynomial invariants, Proceedings of the 23rd International Static Analysis Symposium (SAS), vol.9837, pp.424-446, 2016.
DOI : 10.1007/978-3-662-53413-7_21
URL : https://hal.archives-ouvertes.fr/hal-01358703

F. Santos, A counterexample to the Hirsch conjecture, Ann. of Math, vol.176, issue.1, pp.383-412, 2012.

A. Schrijver, Theory of linear and integer programming, Wiley-Intersci. Ser. Discrete Math. Optim, 1987.

A. Schrijver, Combinatorial Optimization. Polyhedra and Efficiency, Algorithms Combin, vol.24, 2003.

C. Scheiderer, Sums of squares of polynomials with rational coefficients, J. Eur. Math. Soc, vol.18, issue.7, pp.1495-1513, 2016.

C. Scheiderer, Semidefinite representation for convex hulls of real algebraic curves, SIAM J. Appl. Algebra Geom, vol.2, issue.1, pp.1-25, 2018.

, C. Scheiderer. Spectrahedral shadows. SIAM J. Appl. Algebra Geom, vol.2, issue.1, pp.26-44, 2018.

S. Sergeev, Max-plus definite matrix closures and their eigenspaces, Linear Algebra Appl, vol.421, issue.2, pp.182-201, 2007.
DOI : 10.1016/j.laa.2006.02.038
URL : https://doi.org/10.1016/j.laa.2006.02.038

L. S. Shapley, Stochastic games, Proc. Natl. Acad. Sci. USA, vol.39, issue.10, pp.1095-1100, 1953.

S. Smale, Mathematical problems for the next century, Math. Intelligencer, vol.20, issue.2, pp.7-15, 1998.

S. N. Samborski? and G. B. Shpiz, Convex sets in the semimodule of bounded functions, Adv. Soviet Math, vol.13, pp.135-137, 1992.

B. Sturmfels, Viro's theorem for complete intersections, Ann. Sc. Norm. Super. Pisa Cl. Sci, vol.21, issue.4, pp.377-386, 1994.

D. Speyer and L. K. Williams, The tropical totally positive Grassmannian, J. Algebraic Combin, vol.22, issue.2, pp.189-210, 2005.

S. Schewe, A. Weinert, and M. Zimmermann, Parity games with weights, Proceedings of the 27th EACSL Annual Conference on Computer Science Logic (CSL), vol.119, pp.1-36, 2018.
DOI : 10.4204/eptcs.193.0.1
URL : https://doi.org/10.4204/eptcs.193.0.1

T. Theobald, Some recent developments in spectrahedral computation, Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory, pp.717-739, 2017.

S. P. Tarasov and M. N. Vyalyi, Semidefinite programming and arithmetic circuit evaluation, Discrete Appl. Math, vol.156, issue.11, pp.2070-2078, 2008.
DOI : 10.1016/j.dam.2007.04.023
URL : https://doi.org/10.1016/j.dam.2007.04.023

K. Tent and M. Ziegler, A Course in Model Theory, Lect. Notes Log, vol.40, 2012.

L. Vandenberghe, S. Boyd, and S. Wu, Determinant maximization with linear matrix inequality constraints, SIAM J. Matrix Anal. Appl, vol.19, issue.2, pp.499-533, 1998.

T. Van-dijk, Oink: An implementation and evaluation of modern parity game solvers, Proceedings of the 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), vol.10805, pp.291-308, 2018.

L. Van-den-dries and P. Speissegger, The real field with convergent generalized power series, Trans. Amer. Math. Soc, vol.350, issue.11, pp.4377-4421, 1998.

C. Vinzant, Real radical initial ideals, J. Algebra, vol.352, issue.1, pp.392-407, 2012.
DOI : 10.1016/j.jalgebra.2011.11.028
URL : https://doi.org/10.1016/j.jalgebra.2011.11.028

O. Ya and . Viro, Real plane algebraic curves: constructions with controlled topology, Algebra i Analiz, vol.1, issue.5, pp.1-73, 1989.

O. Viro, From the sixteenth hilbert problem to tropical geometry, Jpn. J. Math, vol.3, issue.2, pp.185-214, 2008.

O. Viro, Hyperfields for tropical geometry I. Hyperfields and dequantization, 2010.

J. Vöge and M. Jurdzi?ski, A discrete strategy improvement algorithm for solving parity games, Proceedings of the 12th International Conference on ComputerAided Verification (CAV), vol.1855, pp.202-215, 2000.

J. Watrous, The Theory of Quantum Information, 2018.

V. Weispfenning, The complexity of linear problems in fields, J. Symbolic Comput, vol.5, issue.1-2, pp.3-27, 1988.

H. Wolkowicz, R. Saigal, and L. Vandenberghe, Handbook of Semidefinite Programming. Theory, Algorithms and Applications, vol.27, 2000.

J. Yu, Tropicalizing the positive semidefinite cone, Proc. Amer. Math. Soc, vol.143, issue.5, pp.1891-1895, 2015.
DOI : 10.1090/s0002-9939-2014-12428-2
URL : http://arxiv.org/pdf/1309.6011.pdf

W. Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinite trees, Theoret. Comput. Sci, vol.200, issue.1-2, pp.135-183, 1998.

G. M. Ziegler, Lectures on Polytopes, vol.152, 2007.
DOI : 10.1007/978-1-4613-8431-1

K. Zimmermann, A general separation theorem in extremal algebras. Ekonomickomatematický obzor, vol.13, pp.179-201, 1977.

U. Zwick and M. Paterson, The complexity of mean payoff games on graphs, Theoret. Comput. Sci, vol.158, issue.1-2, pp.343-359, 1996.

, être résolue avec une précision arbitraire en utilisant une hiérarchie de programmes semi-définis. On trouve plus d'informations sur les applications de la programmation semi-définie en optimisation polynomiale dans les livres

, pour plus d'informations sur la programmation semi-définie et ses applications. En pratique, on résout des programmes semi-définis en utilisant des méthodes de points intérieurs. Ces méthodes ont été généralisées de la programmation linéaire à la programmation semidéfinie par Alizadeh, Grâce à sa puissance expressive, la programmation semi-définie a des applications dans la théorie du contrôle [BEGFB94], en information quantique

, Il y a beaucoup des questions ouvertes sur les spectraèdres et la programmation semi-définie. Par exemple, Nemirovski [Nem07] a demandé de caractériser les spectraèdres projetés. Helton et Nie [HN09] ont conjecturé que tout ensemble semi-algébrique convexe est une projection d'un spectraèdre, Nous renvoyons à [dK02, Ren01, GM12] pour plus d'informations sur les méthodes de points intérieurs

, De plus, on sait qu'elle est vraie en dimension 2

L. Cependant, . Conjecture-À-Été-récemment-réfutée-par, and . Scheiderer, qui a montré que le cône des formes semi-définies positives n'est pas une projection d'un spectraèdre, sauf pour quelques cas particuliers [Sch18b]. Son article contient une liste exhaustive de références. La conjecture généralisée de Lax est une autre question ouverte. Elle demande si tout cône d'hyperbolicité est un spectraèdre. La réponse est positive pour plusieurs classes de ces cônes

, Nous renvoyons aux travaux cités pour plus d'informations. La géométrie des spectraèdres a été étudié, Néanmoins, quelques généralisations de la conjecture sont fausses

, Une solution exacte au programme semi-défini est un nombre algébrique et le degré de son polynôme minimal peut être élevé [NRS10]. De plus, les méthodes mentionnées ci-dessus dépendent d'hypothèses supplémentaires sur la structure d'un spectraèdre sous-jacent. Nous renvoyons à [Ram97, dKV16, LMT15] pour plus d'informations et à [LP18] pour une classe de programmes semi-définis de petite taille qui sont difficiles pour les logiciels contemporains. Les méthodes de pointe qui sont capables de résoudre les programmes semidéfinis généraux sont fondées sur les méthodes de points critiques, Cependant, il y a plusieurs questions ouvertes dans cette domaine. Par exemple, on ne comprend pas bien la structure faciale des spectraèdres et des cônes d'hyperbolicité. Dans cette thèse, nous nous intéressons à la complexité théorique de la programmation semidéfinie. Dans le modèle de machine du Turing