Colloquium Mathematics & Computer Science - Prof. O. Lorscheid

Title: Tropical methods in mathematics and computer science

Abstract:

The tropical numbers gained attention, and their name, in the 1980s due to the work of the Brazil-based computer scientist Imre Simon. Since then there is an increasing understanding of how the tropical numbers relate to numerous problems in mathematics and computer science, such as optimization, game theory, sandpiles, matroids, Gromov-Witten theory, chemical reaction networks, deep learning, auctions and many more.

In the first part of this talk, we will introduce the tropical numbers and explain the reason for their ubiquity, which is either the presence of min/max-operations or an approximation by rounding.

In the second part of the talk, we will explain in the exemplary case of dynamic programming how tropical numbers lead to an efficient solution for finding the shortest path on a metric graph. Building up on this, we will extend this principle to find new and fast algorithms to solve mean payoff games, which is work in progress with Akian, Gaubert and Mnich.