Topic and Lectures: The ADYN summerschool consists of lectures on different angles in the modern analysis of algorithms.  The target audience are PhD students and PostDocs with an interest in algorithms and/or combinatorics. Confirmed lecturers are

• Michael Anastos (ISTA)  -  Lecture Title:  Long paths and cycles in random graphs

• Andreas Galanis  (University of Oxford) -  Lecture Title:  Sampling and Phase Transitions

• Torsten Mütze (University of Kassel) - Lecture Title:  Combinatorial generation: graphs, algorithms, algebra and geometry

Our confirmed invited speakers are:

• Charilaos Efthymiou (University of Warwick)
• Matthias Englert (University of Warwick)
• Lisa Hartung (University of Mainz)
• Jan Nagel (TU Dortmund)
• Friedhelm Meyer auf der Heide (Paderborn University)
• Christian Scheideler (Paderborn University)

Date and Time: The summerschool takes place from the 30th June to 4th July 2025. It will start in the morning of the 30th and end at noon on the 4th.

Location: It will take place at Hotel Haus Griese at the Möhnesee lake.

Fee & Cost:

• There will be no participation fee as the school is funded by the DFG Research Unit ADYN FOR 2975 and lunch is provided for all participants.

• Accomodation and travel will be not reimbursed for participants. 

• Participants are invited to book rooms at Hotel Griese but of course, any other venue can be booked as well.  A room at Hotel Griese costs 50 p.P. for double rooms. 

• There is a vegan & vegerian dinner option for 15€/day at Hotel Griese which is not included in the summer school. You can sign up for this via the regestration form. 

Organisers: Petra Berenbrink (Universität Hamburg), Amin Coja-Oghlan (TU Dortmund University),  Martin Hoefer (RWTH Aachen University), Lukas Hintze (Universität Hamburg), Maurice Rolvien (Universität Hamburg), Lena Krieg (TU Dortmund University), and Olga Scheftelowitsch (TU Dortmund University).

Contact: Feel free to contact us via e-mail.

Charilaos Efthymiou

Title: On sampling two spin models using the local connective constant

Abstract: This work establishes novel, optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models . These bounds are expressed in terms of the local connective constant of the underlying graph G. This is a notion of "effective degree" of G on a local scale. Our results have some interesting consequences for bounded degree graphs: include the max-degree bounds as a special case, improve on the running time of the FPTAS considered in [Sinclair, Srivastava, Stefankonvic and Yin: PTRF 2017], allow us to obtain mixing bounds in terms of the spectral radius of the adjacency matrix and improve on results in [Hayes: FOCS 2006], We obtain our mixing bounds by utilising the k-non-backtracking matrix H(G,k). This is a very interesting, alas technically intricate, object to work with. We upper bound the spectral radius of the pairwise influence matrix I_G by means of the 2-norm of H(G,k). To our knowledge, obtaining mixing bound using H(G,k) has not been considered before in the literature.

Matthias Englert

Title: Approximation Guarantees for Shortest Superstrings

Abstract: The Shortest Superstring problem is an NP-hard problem, in which given as input a set of strings, we are looking for a string of minimum length that contains all input strings as substrings. The Greedy Conjecture (Tarhio and Ukkonen, 1988) states that the GREEDY algorithm, which repeatedly merges the two strings of maximum overlap, is 2-approximate. However, the best upper bound known previously was 3.5 Kaplan and Shafrir (IPL 2005), which improved upon the upper bound of 4 by Blum et al. (STOC 1991).
We give a new upper bound of approximately 3.396 for the approximation factor of GREEDY. Additionally, our result implies an algorithm for the Shortest Superstring problem having an approximation guarantee of approximately 2.466, improving upon a gurantee of approximately 2.478 by Mucha (SODA 2013).
(joint work with Nicolaos Matsakis and Pavel Veselý)

Lisa Hartung

Title: The mean field stubborn voter model

Abstract: In this talk, we look at a variant of the voter model in which some voters keep their opinions for a long time, and we are interested in how this affects the consensus time. This is modeled through iid fat-tailed waiting times in the voter model on the complete graph. Our main result is the existence of a limiting infinite voter model on the slowest updating sites. We further derive explicitly the consensus probabilities in the limit model. To prove this, we study properties of the coalescing system of random walks that forms the dual of the limit voter model and proof, among others, coming down from infinity. The talk is based on joint work with C. Mönch (Mainz) and F. Völlering (Leipzig). 

Friedhelm Meyer auf der Heide

Title:  Unifying Gathering Protocols for Swarms of Mobile Robots

Abstract: We survey recent results regarding the Gathering problem in the research area of distributed computing by mobile robots. We assume a simple, standard model of robots: they are point-shaped, live in a d-dimensional Euclidean space, are disoriented (do not agree on common directions or orientations) and have a limited visibility (can only observe other robots up to a constant distance).

The goal of Gathering is to gather all robots at a single, not predefined point. Our focus lies on unifying and extending existing work on gathering in the above model. For this, we derive core properties of protocols that guarantee Gathering and prove runtime bounds that improve upon previous work. We study such strategies for the continuous time model, as well as for the discrete, round-based time model.

Jan Nagel

Title: Random walk on Galton-Watson trees with vanishing conductances

Abstract: We consider limit theorems for a random walk on a weighted Galton-Watson tree, where the edges of the tree are assigned randomly uniformly elliptic conductances and the random walker crosses an edge with probability proportional to its conductance. For this process, the effective speed or variance depend in an intricate way on the law of the conductances. In order to study this dependence, we assign to a positive fraction of edges a small conductance $\varepsilon$. We show a functional central limit theorem for the distance of the walker to the root and, provided that the tree formed by larger conductances is supercritical, we show that the variance is nonvanishing as $\varepsilon\to 0$, which implies an estimate for the slowdown induced by few edges with small conductance. The proof utilizes a specific regeneration structure, which leads to escape estimates uniform in the edge weights.

Christian Scheideler

Title:  Blockchain Made Lightweight: A Median Rule for State Machine Replication

Abstract: I will present a lightweight solution for state machine replication. Specifically, I show how a simple median rule for the stabilizing consensus problem can be adapted to obtain a low-latency solution for state machine replication. In that solution, the servers only need to maintain the part of the state machine pertaining to uncommitted commands, and clients hold certificates for each committed command. The protocol guarantees liveness as long as DoS attacks on the servers remain below a certain threshold, even if performed by an attacker who is just one round late concerning the latest state of the system, but has the ability to quickly recover after a massive DoS attack.