Large-Scale Randomization and Certification

• Applicant: Professor Dr.-Ing. Ulrich Meyer
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 411362735

The main goals of this subproject are two-fold. The first goal is to support the other subprojects of the research unit ADYN with an algorithm engineering approach by complementing and extending the analytical results on algorithms and dynamics. Based on successful collaborations in the first phase, we are planning, for example, to investigate non-trivial extensions of our high-performance simulator for population protocols. We will also explore models and generators for temporal graphs in order to ideally obtain "realistic" and/or analytically comprehensible dynamic network models. Furthermore, we aim to advance the state of the art in theoretical and practical graph algorithms and data structures for massive datasets, focusing on path problems in static and dynamic random graphs. The underlying computational models include classical scenarios (sequential, parallel, memory hierarchies) as well as newer models, such as the processing-in-memory (PIM) architecture. As already started in the first phase, we will complement these questions by investigating the existence of compact and easily understandable "certificates" for correct execution, especially in the context of dynamic graph algorithms.

• DFG Programme: Research Units
• Subproject of: FOR 2975: Algorithms, Dynamics, and Information Flow in Networks