Komplexität von Zählproblemen: GI-Dissertationspreis für Radu Curticapean

Für die beste Informatikdissertation im deutschsprachigen Raum ist in diesem Jahr Dr. rer. nat. Radu Curticapean ausgezeichnet worden. Radu Curticapean promovierte im Jahr 2015 zum Thema „Die einfachen, kleinen und langsamen Dinge zählen: Über die parametrisierte Komplexität von Zählproblemen“ bei Prof. Dr. Markus Bläser an der Universität des Saarlandes.

Die abzählende Kombinatorik ist das Teilgebiet der Mathematik, in dem gezählt wird, auf wie viele Arten sich Bausteine zu komplexeren Gebilden zusammensetzen lassen. So kann man etwa fragen, auf wie viele Arten sich n Objekte in einer Reihe anordnen lassen. Während diese Anzahl noch durch die Fakultät n! = n*(n-1)*(n-2)*...*1 gegeben ist, lassen sich viele andere Größen oft nicht so leicht ausdrücken.

In der statistischen Physik etwa fragt man im Rahmen des Dimer-Modells, wie viele Möglichkeiten sich ergeben, wenn auf einem Gitter angeordnete Atome zu Paaren gruppiert werden sollen. Jedes Atom soll hier mit exakt einem seiner Gitternachbarn eine Bindung eingehen. Für spezielle Gitterarten lässt sich die Anzahl solcher Gruppierungen effizient mit Computern bestimmen.

In der Arbeit sind zum einen neue Methoden entwickelt worden, Varianten des Dimer-Modells und andere kombinatorische Probleme effizient mit Computern zu berechnen. Zum anderen wird für andere Probleme aufgezeigt, dass sie sich nach gängigen Annahmen der Informatik höchst unwahrscheinlich effizient berechnen lassen. Der Schwerpunkt der Arbeit liegt auf dieser "Negativabgrenzung", die innerhalb der theoretischen Informatik als Komplexitätstheorie bekannt ist.

Mit dieser Preisverleihung würdigen die beteiligten Gesellschaften - die Gesellschaft für Informatik e.V. (GI), das German Chapter of the ACM (GCHACM), die Oesterreichische Computer Gesellschaft (OCG) sowie die Schweizer Informatikgesellschaft (SI)- eine herausragende Arbeit, die auf dem Gebiet der Komplexitätstheorie einen nennenswerten Fortschritt darstellt.

Ein Foto des Preisträgers finden Sie hier zum Herunterladen.