Lehrstuhl für Algorithmen und Komplexit?tstheorie

Herzlich Willkommen auf den Seiten des Lehrstuhls für Algorithmen und Komplexit?tstheorie der Universit?t Regensburg! 百利宫_百利宫娱乐平台￥官网er 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. 百利宫_百利宫娱乐平台￥官网er Ansatz geht dann flie?end in die sogenannte algebraische Komplexit?tstheorie über.

Gegenw?rtig arbeitet neben Prof. Dr. Radu Curticapean auch Dr. Cornelius Brand und Dr. Jiaheng Wang als wissenschaftliche 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! 百利宫_百利宫娱乐平台￥官网e 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.