Unsere Gruppe ART verbindet die drei Elemente Algorithmen, Randomisierung und Theorie in unserer Grundlagenforschung zum Lösen verschiedenster Probleme in großen, dynamischen Netzen.

Algorithmik ist die Kunst der Problemlösung. Unsere schnellebige, vernetzte Welt konfrontiert uns alltäglich mit immer komplexeren Problemen auf verschiedensten Ebenen. Beispiele aus unserem alltäglichen Leben umfassen Navigation (“Was ist die schnellste Strecke von Köln nach Hamburg unter der laufenden Berücksichtigung der Verkehrslage?”) oder die Filterung der Informationsflut im Internet (“Google das mal schnell!”). Beides ist für uns inzwischen selbstverständlich, doch dahinter stehen Algorithmen die eine stetig steigende Informationsflut bewältigen müssen, gegen Manipulation geschützt sein müssen und trotz alldem immer schneller Ergebnisse liefern sollen.

Ein Schlüsselelement moderner Algorithmik ist Randomisierung. Diese ermöglicht nicht nur den Entwurf verblüffend einfacher und effizienter Algorithmen, sondern zeigt oft auch ein hohes Maß an Robustheit gegenüber bösartiger Manipulation. Viele Probleme die deterministisch kaum effizient lösbar sind können durch Randomiserung elegant und zuverlässig gelöst werden.

Unser theoretischer Ansatz setzt dabei auf Grundlagenforschung zu beweisbar sicheren und effizienten Algorithmen. Wir widmen uns insbesonder dem Design und der Analyse von Algorithmen in großen dynamischen Netzen. Solche Netze können zum Beispiel reale Netwerke (Rechner im Internet) oder aber auch die Interaktion von Agenten modellieren. Wie kann man zum Beispiel Informationen robust und schnell verteilen? Wie koordiniert man “Schwärme” von einfachen Agenten? Wie können Netzwerknoten mit widersprüchlichen Informationen einen Konsensus erzielen?