MSCS Seminar Calendar

Wednesday May 23, 2018
pdf * Mathematics Computer Science Seminar
Condition numbers in nonarchimedean semidefinite programming and what they say about stochastic mean payoff games
Stephane Gaubert (INRIA and CMAP, Echole Polytechinique)
2:00 PM in SEO 427
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. Solving the latter is a known problem in algorithmic game theory. It has an unsettled complexity, but a number of experimentally efficient algorithms have been developed. We used such stochastic games algorithms to solve generic nonarchimedean semidefinite problems.
We will show that, conversely, one can infer complexity bounds for stochastic games from their tropical formulation. To do so, we develop a metric geometry approach of nonarchimedean semidefinite programming. We use the value of a stochastic mean payoff game to define a nonarchimedean condition number. The latter measures the distance to unfeasibility, for a feasible instance, and vice versa. This condition number coincides with the inverse of the maximal radius of a ball included in the primal or dual feasible set. Here, the radius is measured in Hilbert's projective metric, the canonical metric of tropical convexity. The time needed to decide the winner of a stochastic mean payoff game can be bounded in terms of the condition number and of an auxiliary metric estimate. In this way, we obtain parametrized complexity bounds for several classes of games.
The results on nonarchimedean conditions numbers are from a current work with Allamigeon, Katz, and Skomra, arXiv:1802.07712, based on earlier work with Allamigeon and Skomra, arXiv:1603.06916 (J. Symb. Comp.), arXiv:1610.06746 and arXiv:1801.02089.
Friday September 28, 2018
pdf * Departmental Colloquium
TBA
Holly Krieger (University of Cambridge)
3:00 PM in SEO 636
TBA
Wednesday October 17, 2018
pdf * Statistics Seminar
TBA
Xinyi Li (University of Chicago)
4:00 PM in SEO 636
TBA
Friday October 26, 2018
pdf * Departmental Colloquium
TBA
Alex Wilkie (Manchester)
3:00 PM in SEO 636
Web Privacy Notice HTML 5 CSS FAE
UIC LAS MSCS > seminars > seminar calendar