Unsere Forschung widmet sich vorwiegend Berechnungsproblemen auf abstrakten Netzwerken (sogenannten Graphen), die Relationen zwischen Objekten abbilden, wie sie etwa in sozialen Netzwerken oder Straßennetzen auftreten. Für solche Probleme entwickeln wir Algorithmen mittels mathematischer Methoden aus der Algebra, indem wir beispielsweise Daten in Polynome über bestimmten Körpern übersetzen und diese Daten durch algebraische Manipulationen der assoziierten Polynome weiterverarbeiten. Dieser Ansatz geht dann fließend in die sogenannte algebraische Komplexitätstheorie über.
Unsere Arbeit wird teilweise durch den mit 1.5 Mio. € dotierten ERC Starting Grant COUNTHOM finanziert. In diesem Projekt werden spannende Verbindungen zwischen verschiedenen kombinatorischen Problemen untersucht. Einige fundamentale Berechnungsprobleme, die das Testen und Zählen kleiner Muster in Netzwerken betreffen, wurden nämlich früher unabhängig voneinander untersucht, können aber aus der richtigen Perspektive als ein und dasselbe Problem aufgefasst werden! Diese verallgemeinernde Perspektive wird ermöglicht durch sogenannte Homomorphismen, strukturerhaltende Abbildungen aus der Mathematik. Im COUNTHOM-Projekt werden wir mittels Homomorphismen ein tieferes Verständnis und dadurch auch optimale Algorithmen für solche Berechnungsprobleme entwickeln.
