##### Dagstuhl Seminar 16482

### Algorithms and Effectivity in Tropical Mathematics and Beyond

##### ( Nov 27 – Dec 02, 2016 )

##### Permalink

##### Organizers

- Stéphane Gaubert (INRIA Saclay - Île-de-France, FR)
- Dimitry Grigoriev (Lille I University, FR)
- Michael Joswig (TU Berlin, DE)
- Thorsten Theobald (Goethe-Universität Frankfurt am Main, DE)

##### Contact

- Andreas Dolzmann (for scientific matters)
- Simone Schilke (for administrative matters)

##### Impacts

- Tropical Combinatorial Nullstellensatz and Fewnomials Testing : article in LNCS 10472 : International Symposium on Fundamentals of Computation Theory, FCT 2017 - Grigoriev, Dima; Podolskii, Vladimir V. - Berlin : Springer, 2017. - pp. 284-297 - (Lecture notes in computer science ; 10472 : article).

Tropical mathematics is a uniting name for different research directions which involve the semi-ring of real numbers endowed with the operations {min, +} (called the tropical semi-ring). It has emerged in several areas of computer science and of pure and applied mathematics. This seminar focusses on effective methods, algorithms and complexity bounds in tropical mathematics, and on their relations with open questions in various areas of computer science, including optimization, game theory and circuit complexity. During the seminar, we plan to study the following issues (the list is not exhaustive).

**Tropical linear systems and mean payoff games.** One of the oldest open algorithmic challenges in tropical mathematics is the complexity of solving systems of tropical linear equalities and inequalities. It is known to be equivalent to solving mean payoff games. The solvability of these problems is among the few known problems which are contained in the intersection NP ∩ co-NP, but not currently known to be in P. This leads to new approaches in linear programming or convex semialgebraic programming over nonarchimedean fields.

**Tropical polynomial systems.** Beyond tropical linear systems, much less was done towards tropical polynomial systems. Their solvability is NP-complete analogously to the solvability of classical polynomial equations. A tropical dual version of the weak Hilbert's Nullstellensatz was recently proved which reduces solvability of a tropical polynomial system to a tropical linear one.

**Tropical bases and tropical symbolic computation.** In computer algebra and symbolic computation, Gröbner bases provide an effective means to handle polynomials, with numerous applications such as formal reasoning, robotics, integer linear programming. Their tropical counterparts, tropical bases of tropical varieties, do exist and provide as well a cornerstone of tropical mathematics. They naturally occur when solving a (classical) polynomial system in Newton-Puiseux series, and there exists an algorithm for constructing a tropical basis in the constant-coefficient case. The seminar will discuss the state-of-the-art of tropical bases (complexity bounds, algorithmics).

**Combinatorial complexity.** The seminar will discuss combinatorial aspects of tropical systems. This includes the ranks of tropical matrices and their computation, tropical polyhedra, tropical separation problems, as well as face numbers and Betti numbers of systems of tropical systems.

**Circuit complexity**. Recently, new connections between (max, +) matrix multiplication and circuit complexity have come up. While conventional multiplication of two *n x n*-matrices can be done in time O(2.3729) it is not yet known whether tropical matrix multiplication can be achieved in subcubic time. Moreover, the problem of tropical matrix multiplication belongs to a large collection of problems (including the All-Pairs Shortest Path Problem APSP), which are either all solvable in subcubic time, or none of them ("APSP-hardness"). Using tools from circuit complexity, it has recently been shown that randomized methods allow for faster algorithms.

**Tropical differential equations.** The complexity issues of this recent topic will be discussed, together with basic problems of tropical differential algebraic geometry.

Tropical mathematics is a uniting name for different research directions which involve the semi-ring of real numbers endowed with the operations min, + (called the tropical semi-ring). It has emerged in several areas of computer science and of pure and applied mathematics. For the first time, this seminar brought together the computer science and the mathematics viewpoints. A focus was on effective methods, algorithms and complexity bounds in tropical mathematics, and on their relations with open questions in various areas of computer science, including optimization, game theory and circuit complexity.

One of the oldest open algorithmic challenges in tropical mathematics is the complexity of solving systems of tropical linear equalities and inequalities. It is known to be equivalent to solving mean payoff games. The solvability of these problems is among the few known problems which are contained in the intersection NP cap co-NP, but not currently known to be in P. This leads to new approaches in linear programming or convex semialgebraic programming over nonarchimedean fields.

According to the organizers' points of view the seminar was quite successful. In addition to 28 talks there were many informal discussions and exchange of ideas in small groups. We expect several new common papers of the participants conceived during the seminar. An important feature was to bring together experts with different backgrounds who often knew other participants just by their publications. According to the opinions expressed, the participants learned a lot of new things. The seminar was especially useful for the young people.

Every talk, in addition to new results, also contained open problems. This created a lot of interaction in subsequent discussions. The audience was very active, many questions were posed to the speakers during the talks and the breaks.

- Algorithmical problems of foundations of tropical mathematics (H. Markwig, D. Maclagan, F. Rincon, V. Podolskii);
- Complexity of games and of tropical linear and convex algebra (M. Bodirsky, S. Gaubert, T. Hansen, M. Joswig, G. Loho, M. MacCaig, B. Schröter, S. Sergeev, M. Skomra);
- Algorithms and complexity bounds on tropical varieties (F.Bihan, D. Grigoriev, S. Hampe, A. Jensen, T. Jörgens, L. Tabera, T. Theobald, T. de Wolff). We mention that S. Hampe has made a demonstration of the software Polymake for computations in tropical algebra;
- Algorithms in tropical differential algebra (F. Aroca, C. Garay);
- Interactions of tropical mathematics with algorithmic issues in classical mathematics (M. Akian, X. Allamigeon, Bo Lin, M. Rojas, C. Vinzant).

During the seminar a manuscript appeared (on the Internet) with the very strong claim of a quasi-polynomial complexity algorithm for parity games. It was a lucky coincidence that so many experts with various backgrounds were present. So a special evening session on Thursday was created to analyze this result and its ramifications. This was one more highlight.

- Marianne Akian (INRIA Saclay - Île-de-France, FR) [dblp]
- Xavier Allamigeon (INRIA Saclay - Île-de-France, FR) [dblp]
- Fuensanta Aroca (Universidad Nacional Autonoma - Mexico, MX)
- Frédéric Bihan (University Savoie Mont Blanc - Le Bourget-du-Lac, FR) [dblp]
- Manuel Bodirsky (TU Dresden, DE) [dblp]
- Timo de Wolff (Texas A&M University - College Station, US) [dblp]
- Cristhian Garay (Fluminense Federal University - Rio de Janeiro, BR)
- Stéphane Gaubert (INRIA Saclay - Île-de-France, FR) [dblp]
- Dimitry Grigoriev (Lille I University, FR) [dblp]
- Alexander Guterman (Moscow State University, RU) [dblp]
- Christian Haase (FU Berlin, DE) [dblp]
- Simon Hampe (TU Berlin, DE) [dblp]
- Thomas Dueholm Hansen (Aarhus University, DK) [dblp]
- Anders Jensen (Aarhus University, DK) [dblp]
- Thorsten Jörgens (Goethe-Universität - Frankfurt a. M., DE)
- Michael Joswig (TU Berlin, DE) [dblp]
- Bo Lin (University of California - Berkeley, US) [dblp]
- Georg Loho (TU Berlin, DE) [dblp]
- Marie MacCaig (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Diane Maclagan (University of Warwick - Coventry, GB) [dblp]
- Hannah Markwig (Universität Tübingen, DE) [dblp]
- Thomas Markwig (Universität Tübingen, DE) [dblp]
- Vladimir Podolskii (Steklov Institute - Moscow, RU) [dblp]
- Felipe Rincon (University of Oslo, NO) [dblp]
- J. Maurice Rojas (Texas A&M University - College Station, US) [dblp]
- Benjamin Schröter (TU Berlin, DE) [dblp]
- Sergei Sergeev (University of Birmingham, GB) [dblp]
- Mateusz Skomra (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Luis Tabera (University of Cantabria, ES) [dblp]
- Thorsten Theobald (Goethe-Universität Frankfurt am Main, DE) [dblp]
- Cynthia Vinzant (North Carolina State University - Raleigh, US) [dblp]

##### Classification

- data structures / algorithms / complexity
- optimization / scheduling

##### Keywords

- algorithms in tropical mathematics
- complexity
- effective bounds
- optimization
- zero-sum games