Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS138: Computational aspects of tropical geometry
Time:
Tuesday, 09/Jul/2019:
3:00pm - 5:00pm

Location: Unitobler, F013
53 seats, 74m^2

Presentations
3:00pm - 5:00pm

Computational aspects of tropical geometry

Chair(s): Georg Peter Loho (London School of Economics), Ngoc Mai Tran (University of Texas), Yue Ren (Max Planck Institute for Mathematics in the Sciences, Germany), Kalina Mincheva (Yale University, USA)

The aim of this session is to demonstrate the effictive use of tropical geometry to tackle problems from optimization and various applications.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming

Xavier Allamigeon1, Stéphane Gaubert1, Ricardo Katz2, Mateusz Skomra3
1INRIA & CMAP, 2CONICET-CIFASIS, 3École normale supérieure de Lyon

Semidefinite programming can be considered over any real closed field, including fields of Puiseux series equipped with their nonarchimedean valuation. Nonarchimedean semidefinite programs encode parametric families of classical semidefinite programs, for sufficiently large values of the parameter. Recently, a correspondence has been established between nonarchimedean semidefinite programs and stochastic mean payoff games with perfect information. This correspondence relies on tropical geometry. It allows one to solve generic nonarchimedean semidefinite feasibility problems, of large scale, by means of stochastic game algorithms.
In this talk, we show that the mean payoff of these games can be interpreted as a condition number for the corresponding nonarchimedean feasibility problems. This number measures how close a feasible instance is from being infeasible, and vice versa. We show that it coincides with the maximal radius of a ball in Hilbert's projective metric, that is included in the feasible set. The geometric interpretation of the condition number relies in particular on a duality theorem for tropical semidefinite feasibility programs.
Then, we bound the complexity of the feasibility problem in terms of the condition number. We finally give explicit bounds for this condition number, in terms of the characteristics of the stochastic game. As a consequence, we show that the simplest algorithm to decide whether a stochastic mean payoff game is winning, namely value iteration, has a pseudopolynomial complexity when the number of random positions is fixed. Joint work with Stéphane Gaubert, Ricardo D. Katz and Mateusz Skomra.

 

Computing tropical hypersurface intersections

Anders Jensen
Aarhus University

A tropical hypersurface is a balanced polyhedral complex of codimension 1 while a tropical prevarity is a finite intersection of such hypersurfaces. The dynamic enumeration strategy for prevarity computation proposed by Mizutani, Takeda and Kojima (2006) appears in the context of polyhedral homotopy continuation in polynomial system solving. It produces the prevariety for zero-dimensional intersections in general position. In contrast, the non-generic situation is more involved as the intersection may be non-pure and numerical exactness becomes critical. Extending joint work with Sommars and Verschelde we propose a dynamic decomposition strategy for reducing the number of vertices in the enumeration tree. We report on experimental results with our implementation.

 

Algebraic systems and exterior semi-algebras

Letterio Gatto1, Lois Rowen2
1Politecnico di Torino, 2Bar-Ilan University

In this talk, we describe negation maps and ``systems,'' and their application to Grassmann (exterior) algebra in a rather general framework that includes tropical algebra, hyperfields, and fuzzy rings.
The usual definition of Grassmann (exterior) algebras generalizes directly to semi-algebras, and has a built-in negation map for elements of degree greater equal 2, so the theory of systems can be applied directly to Gatto's theory, unifying results of linear algebra from different perspectives including the classical perspective. We continue with a systemic version of Schubert derivations and the corresponding cohomology.
This also relates to joint work on linear algebra with Akian and Gaubert, and on homology with Jun and Mincheva.

 

Tropical volume by tropical Ehrhart polynomials

Matthias Schymura
EPFL

We are motivated by the problem of intrinsically defining a volume concept for tropical polytopes. In Euclidean space, the number of integral points contained in a large dilate of a given polytope approximates its volume. Even more, by Ehrhart's theorem, the function that counts integral points in dilates of an integral polytope is a polynomial in the dilation factor, whose leading coefficient equals the volume of the polytope. After introducing a suitable and natural concept of a tropical lattice, we aim to establish an analogous result for tropical lattice polytopes based on their covector decomposition.