The tropicalization of non-archimedean convex semialgebraic sets and its relation with mean payoff games

Seminar
Speaker
Prof. Stephane Gaubert (INRIA and CMAP, Ecole Polytechnique, IP Paris, CNRS)
Date
07/04/2021 - 11:30 - 10:30Add to Calendar 2021-04-07 10:30:00 2021-04-07 11:30:00 The tropicalization of non-archimedean convex semialgebraic sets and its relation with mean payoff games 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 tropicalizations of polyhedra and spectrahedra are of special interest, 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 semialgebraic convex optimization 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, especially:   [1] X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig, What Tropical Geometry Tells Us about the Complexity of Linear Programming, SIAM review, 63(1), 123--164 (2021). [2] X. Allamigeon, S. Gaubert, and M. Skomra. Tropical spectrahedra, Discrete Comput. Geom., 63, 507--548 (2020)   =============================================   Topic: BIU Algebra Seminar -- Gaubert Time: Apr 7, 2021 10:30 AM Jerusalem   Join Zoom Meeting https://us02web.zoom.us/j/86395250325   Meeting ID: 863 9525 0325     Zoom -- see invitation below אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Zoom -- see invitation below
Abstract
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 tropicalizations of polyhedra and spectrahedra are of special interest, 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 semialgebraic convex optimization 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, especially:
 
[1] X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig,
What Tropical Geometry Tells Us about the Complexity of Linear Programming, SIAM review, 63(1), 123--164 (2021).
[2] X. Allamigeon, S. Gaubert, and M. Skomra. Tropical spectrahedra, Discrete Comput. Geom., 63, 507--548 (2020)
 
=============================================
 
Topic: BIU Algebra Seminar -- Gaubert
Time: Apr 7, 2021 10:30 AM Jerusalem
 
Join Zoom Meeting
 
Meeting ID: 863 9525 0325
 

 

Last Updated Date : 30/03/2021