University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > Condition numbers in nonarchimedean semidefinite programming and what they say about stochastic mean payoff games

## Condition numbers in nonarchimedean semidefinite programming and what they say about stochastic mean payoff gamesAdd to your list(s) Download to your calendar using vCal - Stephane Gaubert (INRIA and Ecole Polytechnique, France)
- Thursday 24 January 2019, 16:00-17:00
- Nuffield G17.
If you have a question about this talk, please contact Sergey Sergeev. This talk is a part of the LMS Workshop on Tropical Mathematics and its Applications Semidefinite programming consists in optimizing a linear form over a spectrahedron, the latter being a cross section of the cone of positive semidefinite matrices. This makes sense over any real closed field, and in particular, over fields of real Puiseux series, equipped with their non archimedean valuation. In this way, a tropical spectrahedron can be defined as the image by the valuation of a nonarchimedean spectrahedron. The nonarchimedean semidefinite feasibility problem, with generic valuations of the input matrices, turns out to be equivalent to stochastic mean payoff games with perfect information. We use this correspondence to define a condition number for stochastic mean payoff games, which controls the ``rotundity’’ of the associated tropical spectrahedra. We bound the complexity of value iteration in terms of this condition number, and derive fixed parameter tractability results for stochastic mean payoff games with perfect information. This is a joint work with Xavier Allamigeon, Ricardo Katz and Mateusz Skomra. This talk is part of the Optimisation and Numerical Analysis Seminars series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsLab Lunch Cargo Computer Science Lunch Time Talk Series## Other talksLovĂˇsz' Theorem and Comonads in Finite Model Theory Best Response Dynamics on Random Graphs Generalised hydrodynamics and universalities of transport in integrable (and non-integrable) spin chains Quantum simulation of strongly correlated fermions: A theory perspective |