02.04.2025, 14.15 Uhr
Vortragender: Matthias Artmann

Title: On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits

Abstract: In programmable matter, we consider a large number of tiny, primitive computational entities called particles that run distributed algorithms to control global properties of the particle structure. In this paper, we study the shape containment problem, where the particles are given a description of a shape S and have to find maximally scaled representations of S within their initial configuration. We use the geometric amoebot model for programmable matter with its reconfigurable circuit extension, which allows the instantaneous transmission of primitive signals on connected subsets of particles.
We first prove a lower runtime bound of Omega(sqrt(n)) synchronous rounds for the general problem, where n is the number of particles. Then, we construct the class of snowflake shapes and its subclass of star convex shapes, and present solutions for both. Let k be the maximum scale of the considered shape in a given amoebot structure. If the shape is star convex, we solve it within O(log^2 k) rounds. If it is a snowflake but not star convex, we solve it within O(sqrt(n) log n) rounds.
In this talk, I will give a brief overview of the shape containment problem and the construction of snowflake shapes.

23.07.2025, 14.00 Uhr
Vortragender: Henning Hillebrandt 

Title: A New Algorithm for Exact SSSP in Hybrid Networks

Abstract: Computing Single-Source Shortest Paths (SSSP) is a fundamental problem in distributed computing and an important building block for many distributed algorithms. In this talk, I present a new algorithm for solving the exact SSSP problem in the HYBRID network model. The algorithm computes exact shortest paths in weighted, directed graphs in time Õ(n^(1/3)), with high probability, matching the best-known result by Censor-Hillel et al. [STACS '21] despite only needing a local capacity of λ = Θ(|E|/n^(1/3)). It builds upon the SSSP framework from Forster and Nanongkai [FOCS '18], which was originally designed for the CONGEST model. The result is obtained through an efficient HYBRID implementation of their generic SSSP algorithm. To this end, I show how to compute a (1+o(1))-approximate solution of the h-hop-limited k-Source-Shortest Paths problem in weighted, directed graphs in time Õ(k + h^(1/2)), with high probability.

06.08.2025, 14.00 Uhr
Vortragender: Alexander Nickel, Antrittsvortrag Master bei M. Fischer 

Title: Know Your Limit - Frame Time Estimation for 3D Realtime Applications

Abstract: In dieser Arbeit soll ein Algorithmus entwickelt werden, der im Rahmen der folgenden Technologien und Hardware, die Renderingzeit (GPU Zeit) eines beliebigen Frames, einer beliebigen Szene, in einer beliebigen Anwendung auf einem beliebigen Computer abschätzt. Die Technologien, die untersucht werden, sind die Texturen Verarbeitung, Lichtberechnung, Schattenberechnung, Ray Tracing und Antialiasing. Diese Eigenschaften werden mithilfe der Grafik Engine Software Godot untersucht. Eine moderne und beliebte Open Source Grafik Engine neben Unreal Engine und Unity die Grafik-APIs wie Vulkan verwendet. Für die Untersuchung werden im ersten Schritt nur die Computer eingesetzt, die mir von der Arbeitsgruppe „Algorithmen und Komplexität“ bereitgestellt wurden. Des Weiteren werden die Technologien, die in meiner Bachelorarbeit „Entwicklung und Analyse von Formeln zur Abschätzung der Renderingzeit eines Frames“ untersucht wurden, mit untersucht. Hierbei handelt es sich um eine Formel, die mithilfe von Knoten, Dreiecken, Vertex-Buffer-Objects (VBOs) und Surfels eine Framezeit (GPU Zeit) abschätzen kann.
 

06.08.2025, 14.30 Uhr
Vortragender: Thilo Berger, Antrittsvortrag Master 

Title: Comparing Existing Methods to Efficiently Place Drones to Connect Isolated Communication Clusters

Abstract: The problem setting is the following: we have many nodes which are randomly distributed over some space and which are able to communicate with each other if they are in close proximity. These distributed communication cluster have to be separately connected via edges to enable global communication. Our goal is to minimize the resulting cost. My masterthesis aims to implement and compare different approaches for the resulting sub-problems.

20.08.2025, 14.00 Uhr
Vortragende: Priyanka Giri

Title: Near-Shortest Path Routing in Hybrid Communication Networks Using Python

Abstract: This thesis presents a grid-based abstraction framework to optimize pathfinding in large-scale hybrid networks, where nodes operate over hybrid communication network. By mapping complex Unit Disk Graph (UDG) topologies to structured grid graphs, the study significantly reduces computational complexity while preserving essential connectivity. The work evaluates Dijkstra’s, Bellman-Ford, and A* algorithms using Python’s NetworkX, analyzing metrics such as path efficiency, computation time, scalability, and packet transmission success rate. Results show that the proposed approach enhances routing performance and scalability without compromising path quality, offering practical applications in vehicular networks, IoT systems, and large-scale wireless infrastructures.

27.08.2025, 14.00 Uhr
Vortragender: Ibrahim Abdul Rahman, Antrittsvortrag Bachelor, bei Matthias Fischer

Title: Effiziente Datenstrukturen und Algorithmen für die Kollisionserkennung im zweidimensionalen Raum 

Abstract: Diese Arbeit untersucht und vergleicht drei etablierte Datenstrukturen – Quadtrees, Bounding Volume Hierarchies (BVH) und Uniform Grids – im Kontext der 2D-Kollisionserkennung. Ziel ist es, ihre Effizienz, Anpassungsfähigkeit und Skalierbarkeit in unterschiedlichen Anwendungsszenarien zu analysieren, etwa bei vielen kleinen oder wenigen großen Objekten. Dazu wird eine eigens in C++ entwickelte 2D-Spielplattform als Testumgebung eingesetzt, die präzise Messungen von Laufzeit und Speicherverbrauch ermöglicht. Die Experimente erlauben eine differenzierte Bewertung der Stärken und Schwächen der einzelnen Ansätze und zeigen gezielte Optimierungspotenziale auf. Die Ergebnisse liefern nicht nur wissenschaftliche Erkenntnisse, sondern auch praxisrelevante Empfehlungen zur Wahl geeigneter Datenstrukturen in Echtzeitanwendungen.

15.10.2025, 14.00 Uhr
Vortragender: Felix Werner (Bachelor)

Title: Monoton erreichbarer Delaunaygraph

Abstract: In diesem Vortrag präsentiere ich das Monotonous-Delaunay-Protokoll, einen lokalen, selbststabilisierenden Algorithmus zur Konstruktion des Delaunaygraphen in verteilten Systemen, der zusätzlich monotone Erreichbarkeit für Broadcast-Operationen garantiert. Das Protokoll ersetzt die bislang gierige Weiterleitung durch eine doppelte sichere Weiterleitung: Knoten leiten Referenzen an je zwei lokale Delaunaynachbarn weiter und schließen die Weiterleitung erst ab, wenn beide Nachbarn durch Acknowledgements bestätigt haben. Dieses Verfahren stellt sicher, dass einmal erreichte Knoten bei identischen zukünftigen Broadcasts ebenfalls erreicht werden. Ich skizziere, warum mit dem Protokoll jede zusammenhängende Starttopologie zu einem Delaunaygraphen konvergiert; die obere Worst-Case-Schranke für die Konvergenz beträgt O(n^3) Runden (mit einer Verbesserung auf O(n), falls die Anfangstopologie bereits einen Delaunaygraphen enthält). Zudem sind die Kosten für dynamische Änderungen wie das Hinzufügen und Entfernen von Knoten lokal begrenzt. Wichtige technische Elemente sind das ackBuffer-Konzept und Mechanismen zur Vermeidung von Deadlocks und doppelten Nachrichten. Damit stellt das Monotonous-Delaunay-Protokoll eine Lösung dar, die formale Korrektheit und robuste, verteilte Broadcasts vereint und durch ihr anwendungsnahes Design eine einfache praktische Implementierung ermöglicht.
 

12.11.2025, 14.00 Uhr
Vortragender: Marcel Opiela (Antrittsvortrag Bachelor)

19.12.2025, 17.00 Uhr
Vortragender: Stefan Schmid, TU Berlin 

Title: A Merry Get-Together in Datacenters

Abstract: Communication patterns in datacenters feature much spatial and temporal structure.This can be exploited for improved resource allocation and performance.In this talk, I will present a fundamental problem underlying such optimized datacenter: the dynamic balanced repartitioning problem. We ask: how can frequently communicatingnodes dynamically "get together", in an offline or even online manner, to reduce communication costs while accounting for reconfiguration costs? I will give an overview of what we know about this recent problem and what are avenues for future research. 

11.02.2026, 14.00 Uhr
Vortragender: Nils Pape (Antrittsvortrag Bachelor) 

Title: Graph coloring in different amoebot models

Abstract: The thesis aims to solve graph-coloring problems within different variations of the amoebot model,
an abstraction of programmable matter, where a each vertex is a assigned a color matching no
neighboring color. Understanding efficient coloring using the underlying structure and restrictions of
the amoebot model and comparison with other distributed algorithms is essential for developing
higher level algorithms. The central question of the paper is how can we efficiently color the graph
induced by regions of amoebots, where many neighboring amoebots build a region and a structure of
many of these regions have to be colored and what is the least amount of colors we can use, while not
increasing the runtime too much. 

11.02.2026, 14.15 Uhr
Vortragender: Thilo Berger (Master)

Title: Comparing Existing Methods to Efficiently Place Drones to Connect Isolated Communication Clusters

Abstract: Drones are increasingly used in diverse scenarios, from disaster response to temporary communication support in isolated networks. 
This thesis investigates a theoretical framework in which drones act as communication pathways to connect separated local networks, abstracted as nodes in a two-dimensional Euclidean space.
Nodes with a certain proximity can freely communicate forming connected components (CC), while connecting distant nodes incurs a cost proportional to the distance, representing the usage of drones.
We address two sub-problems: identifying nodes that can communicate via free edges (connectivity) and determining which additional edges are needed to enable communication between all nodes (minimum spanning tree, MST). 
We also consider a dynamic setting, where node movement causes network connections to change over time.
For dynamic connectivity, we implemented a baseline breadth-first search, a forest-based approach, and an Euler tour tree method, and we also describe a more advanced top-tree approach. 
While for the MST problem we implemented one dynamic approach as well as two approximation approaches with slight variations.
We evaluated the algorithms on networks with up to 200 nodes, varying node density, placement patterns, grid sizes, and CC counts. 
Performance largely depends on the number and size of connected components. 
For dynamic connectivity, Lazy CC performs best for small CCs, while Euler tour trees excel with larger CCs. 
For MSTs, dynamic algorithms outperform Kruskal as CC count increases, and approximation algorithms achieve significant speedups for some additional cost.
Overall, our results provide a systematic experimental analysis of dynamic connectivity and MST algorithms in abstract drone network scenarios and offer guidance for selecting algorithms depending on network characteristics.