Kolloquium So2018

Komplexitätstheorie und effiziente Algorithmen sind ein zentraler Bestandteil der heutigen Informatik. Zur Grundausbildung jedes Informatikers gehören Methoden um algorithmische Lösungen für Optimierungsprobleme zu entwickeln und diese im Hinblick auf ihre Effizienz und Qualität zu analysieren. Wir werden darin geschult von realen Problemen zu abstrahieren, die inhärente Problemkomplexität heraus zu kondensieren und beweisbar gute Lösungsverfahren zu entwerfen – oder zu beweisen, dass das vorliegende Problem nicht effizient lösbar ist.

Der Arbeitsbereich „Theorie Effizienter Algorithmen“ (TEA) untersucht die inhärente Problemkomplexität in verschiedenen Bereichen, wie z.B. im verteilten Rechnen (wo wir uns mit dem Informationsfluss in großen, komplexen Netzwerken beschäftigen), in der Ressourcenverteilung in Rechenzentren und im Cloud Computing (wo die zur Verfügung stehenden Ressourcen unter wirtschaftlichen Gesichtspunkten verteilt werden müssen) oder auch in autonomen mobilen Systemen (wo wir untersuchen wie komplexe, globale Aufgaben durch eine Vielzahl einfacher, lokal agierender Agenten durchgeführt werden können). In meinem Vortrag werde ich verschiedene dieser Bereiche beleuchten und unsere aktuellen Forschungsfragen und -anstrengungen erläutern.

--------

Complexity theory and efficient algorithms are a central pillar of modern computer science. Part of the basic education of any computer scientist is to learn to design algorithmic solutions for optimization problems and to reason formally about the efficiency and quality of these algorithms. We learn to look at a real-world problem, to distill and formalize the inherent difficulty in solving the problem, and to either design provably good solutions for them or to prove the impossibility of finding such solutions.

The research group “Theory of Efficient Algorithms” (TEA) studies the inherent problem complexity in areas like distributed computing (where we deal with the information flow in huge, complex networks), resource management in data centers and in the cloud (where available resources must be distributed in an economic manner, even if we have incomplete information about the current or future system and workload characteristics), and autonomous mobile systems (where we study how simple agents with a locally restricted perception can cooperate to achieve a global goal). My talk will survey recent research efforts and progress
in these areas.