Prof. Manuel Bodirsky erhält ERC Consolidator grant

Prof. Dr. Manuel Bodirsky (Professur Algebra und Diskrete Strukturen) erhält den ERC Consolidator Grant in Höhe von ca. 1,5 Millionen Euro für sein Projekt „Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones“ (CSP-Infinity). Eine Besonderheit ist, dass es sich um ein Projekt aus dem Panel PE6 – Computer Science - handelt, welches aber am Institut für Algebra durchgeführt wird. Constraint Satisfaction Probleme sind Berechnungsprobleme, die in vielen Gebieten der theoretischen Informatik eine wichtige Rolle spielen. Die Übergänge zwischen theoretischer Informatik und Mathematik sind hierbei fließend. Ziel des Projektes ist, die Berechnungskomplexität von Constraint Satisfaction Problemen auf unendlichen Wertebereichen zu verstehen. Vorarbeiten haben gezeigt, dass sich der Unterschied zwischen einfachen und schweren Constraint Satisfaction Problemen mit Hilfe von topologischen Klonen beschreiben lässt. Die Vision von Bodirskys Projekt besteht nun darin, effektive Kriterien aufzustellen, die entscheiden, ob ein CSP mit Hilfe von effizienten Algorithmen gelöst werden kann.