Tropical · Tropical methods in MAthematics and Computer Science
Horizon 2020 — Marie Skłodowska-Curie Actions
- Duration
- 2021-04-01 → 2023-03-31
- EU contribution
- €187,572
- Participants
- 1
- Scheme
- MSCA-IF
Lines connect the coordinator with its partners.
Results in brief
Tropical methods in MAthematics and Computer Science
Tropical arithmetic has been introduced by the computer scientist Imre Simon, and its name is inspired by Simon’s residency in Brazil. The basic idea is simple: optimization problems involve naturally the minimization (sometimes maximization) operation. Replacing usual addition and multiplication of real numbers by minimum and addition, respectively, leads to tropical matrix calculus and tropical varieties. The advantage of tropical arithmetic is that it is easy to solve (number theoretic problems become combinatorial problems) and that the operations are fast to compute (minimum and addition are linear in the size of the input, multiplication is quadratic). A striking example of an every day’s life application are tropical algorithms for the scheduling of trains, which incidentally found a pioneering model for the Dutch railroad system. Our scientific proposal touches three themes around tropical arithmetic: algorithm development, structural insights into matroids and computational tools for algebraic geometry. In more detail, these are: (1) Tropical methods in game theory. The objective is the development of new and fast algorithms to solve mean payoff games. We investigate strategies to solve the “P versus NP”-problem for mean payoff games. (2) Tropical structures for matroids. The objective is to continue a recent approach to matroid representation that is based on a novel type of algebraic object, which is called a pasture. (3) Tropical Riemann-Roch (D3.1–D3.4). The objective is to develop a cohomological understanding of the tropical Riemann-Roch theorem that is based on tropical scheme theory.
Data: CORDIS, © European Union
Project objective
This proposal joins three themes around tropical arithmetics: WP1. Tropical methods in game theory.Mean payoff games form an interesting class in complexity theory since they are known to be in NP, but it is not known whether they can be solved in polynomial time. Our objective is to use tropical operators for the development of new and fast algorithms to solve mean payoff games. In addition, we search for strategies to establish a polynomial time algorithm.WP2. Tropical structures for matroids. In a recent paper, we have introduced a novel approach to study matroid representation in terms of a new algebraic structure: the representation theory of the matroid is completely controlled by its ""foundation"". Our objective is to continue this powerful theory by broadening the foundations and developing computational tools to determine the foundation of a matroid. Additionally, we aim for an understanding of foundations of 3-connected matroid, which conjecturally reveals a deep connectivity property for the foundation.(3) Tropical Riemann-Roch.The tropical Riemann-Roch theorem has found important applications in Brill-Noether theory. Up to date, this theorem is a purely combinatorial statement about graphs. Our objective is to use the richer structure of tropical scheme to develop a cohomological understanding and proof of the Riemann-Roch theorem. This involves the development of sheaf cohomology and etale morphisms for tropical schemes and an understanding of Berkovich skeleta as tropical schemes.Due to the interdisciplinary nature of this proposal (game theory and matroids form a part of computer science, our methods stem from a mathematical background), we chose Groningen as a basis to perform this proposal. The Bernoulli Institute in Groningen merges Mathematics and Computer Science in one departent, with three additional centers AI, CDSS and CogniGron. Moreover the BI hosts virtually all tropical geometers of the Netherlands.""
Original text from CORDIS.
Participants
- RIJKSUNIVERSITEIT GRONINGEN · GroningenCoordinatorNetherlands
Links
Data: CORDIS, © European Union