Dec 2 – 3, 2020
Le Bois-Marie
Europe/Paris timezone

Tropical Convexity, Mean Payoff Games and Nonarchimedean Convex Programming

Dec 3, 2020, 10:00 AM


Stéphane Gaubert (INRIA and CMAP Ecole Polytechnique)


Convex sets can be defined over ordered fields with a non-archimedean valuation. Then, tropical convex sets arise as images by the valuation of non-archimedean convex sets. The tropicalization of polyhedra and spectrahedra are of special in- terest, since they can be described in terms of deterministic and stochastic games with mean payoff. In that way, one gets a correspondence between classes of zero- sum games, with an unsettled complexity, and classes of semilagebraic convex op- timization problems over non-archimedean fields. We shall discuss applications of this correspondence, including a counter example concerning the complexity of interior point methods, and the fact that non-archimedean spectrahedra have precisely the same images by the valuation as convex semi-algebraic sets. This is based on works with Allamigeon, Benchimol, Joswig and Skomra.

Presentation materials