Evènement pour le groupe Séminaire Méthodes Formelles

Date 2019-12-17  07:00-07:00
TitreUsing tropical geometry to obtain condition numbers of stochastic mean payoff games 
RésuméIn this talk, we introduce a condition number of stochastic mean payoff games. To do so, we interpret these games as feasibility problems over tropically convex cones. In this setting, the condition number is defined as the maximal radius of a ball in Hilbert's projective metric that is included in the (primal or dual) feasible set. We show that this conditioning controls the number of value iterations needed to decide whether a mean payoff game is winning. In particular, we obtain a pseudopolynomial bound for the complexity of value iteration provided that the number of random positions is fixed. We also discuss the implications of these results for convex optimization problems over nonarchimedean fields and present possible directions for future research. The talk is based on joint works with X. Allamigeon, S. Gaubert, and R. D. Katz. 
OrateurMateusz Skomra 
UrlENS Lyon 

Aucun document lié à cet événement.

Retour à l'index