Lehrstuhl für Algorithmen und Komplexitätstheorie

Herzlich Willkommen auf den Seiten des Lehrstuhls für Algorithmen und Komplexitätstheorie der Universität Regensburg! Dieser neu gegründete Lehrstuhl an der Fakultät für Informatik und Data Science der Universität Regensburg untersucht die inhärente Komplexität von fundamentalen Berechnungsproblemen. Besondere Schwerpunkte unserer Arbeit liegen auf Zählproblemen sowie damit verwandten Fragestellungen der algebraischen Komplexitätstheorie. Wir nutzen auch Methoden der parametrisierten Komplexitätstheorie.

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.

Gegenwärtig arbeitet neben Prof. Dr. Radu Curticapean auch Dr. Cornelius Brand als wissenschaftlicher Mitarbeiter am Lehrstuhl, unterstützt von Sekretärin Annett Reisinger. Weitere Mitarbeiter werden folgen.

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.