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.

Date and Time: 1st  -  5th June 2026.
Start in the morning of the 1st June
End at noon on the 5th June

Registration is now closed!

Confirmed lecturers:

• Tyler Helmuth (Durham University) - Lecture Title: Equilibrium Statistical Mechanics
• Seffi Naor (Technion University) - Lecture Title: The multifacets of covering problems
• Nick Wormald (Monash University) - Lecture Title: Switching methods for exactly uniform sampling and enumeration
   

Confirmed invited speakers:

• George Giakkoupis (Rennes University) - Title: Distributed Stochastic Graph Algorithms
• Lisa Hartung (University of Mainz) - Title: The voter model with influencers
• Misha Isaev (UNSW) - Title: Fast and irregular: generation of graphs with given degrees.
• Christian Scheideler  (Paderborn University) - Title: The Effect of Faults on Network Expansion
• Fiona Skerman (Uppsala University) - Title: Community detection and the overlap gap property
• Dan Vilenchik (Ben-Gurion University) - Title: From Local Messages to Global Reasoning: What Do Graph Neural Networks Really Learn in
  Combinatorial Optimization?

Location: It will take place at Hotel Haus Griese at the Möhnesee lake.  To book a room,  write a mail to Haus Griese post@hotel-haus-griese.de with all necessary booking information and “ADYN Summerschool” in the subject.

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.
• Dinner is not included in the summer school. 
   

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),  Olga Scheftelowitsch (TU Dortmund University), Kostas Zampetakis  (TU Dortmund University) and Pavel Zakharov (TU Dortmund University).

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

Lectures

Tyler Helmuth

Title: Equilibrium Statistical Mechanics
Abstract: Statistical mechanics aims to explain the emergence of simple
rules governing the large-scale behaviour of systems of huge numbers of
interacting objects. A significant part of modern probability theory is
concerned with developing a mathematical understanding of important
examples. These lectures will be an introduction to discrete statistical
mechanics, via examples, with an eye towards techniques and results that
have proven useful in combinatorics and theoretical computer science:
phase transitions; uniqueness methods; expansions; duality.

Seffi Noar

Title:  The multifacets of covering problems.

Nick Wormald

Title:  Switching methods for exactly uniform sampling and enumeration.
Abstract: In these talks we will examine switching methods  for generating a random sample from the precisely uniform distribution. The requirement of exact uniformity rules out the Markov Chain Monte Carlo approach often used for approximately uniform sampling, and restricts the options considerably.

A switching is usually defined as a specific type of local perturbation of a graph, though more general perturbations will also be considered. Essentially all of the applications involve some type of graphs with given degrees or related structures such as Latin rectangles. Along the way we will experience the close relationship with asymptotic enumeration; there are also uses of switchings for proving properties of random graphs. A central theme will be to highlight the various techniques that have been developed for random sampling by these methods, as well as their strengths and limitations.

 

Invited Talks

George Giakkoupis

Title: Distributed Stochastic Graph Algorithms

Lisa Hartung

Title: The voter model with influencers
Abstract: We study the behaviour of a voter model (with two opinions) with influencers. These are agents
who never change their opinion but pass it on to others. We study the expected crossover time in the
model as well as its scaling limit. In particular, we discuss how the answers depend on the number of
influencers. The talk is based on joint work with Ernst Althaus and Rebecca Steiner.

Misha Isaev

Title: Fast and irregular: generation of graphs with given degrees.
Abstract: The pairing model provides an efficient way to generate a multigraph with given degrees. The resulting distribution is not uniform, but it is uniform within a subset of multigraphs with specified number of double edges, triple edges, etc. We refer to such subsets as strata.   The switching operation introduced by McKay and Wormald creates a flow between the strata reducing multiple edges until we reach simple graphs. The problem is that different graphs might have different number of switching so certain rejections are necessary to maintain the uniformity of the distribution along the process. To guarantee that the rejections won’t fail all the time, an upper bound $o(m^{1/3})$ for the maximum degree  $o(m^{1/3})$ is required, where m is the number of edges. Also, computing the correct rejection probabilities is computationally more expensive so the resulting algorithm is superlinear, unlike the configuration model. In a series of later works, Gao and Wormald realised that to guarantee that the output is a uniform simple graph, it is sufficient to keep track of the expected number of visits which opened the door for more complicated switching schemes involving increasing the number of multiple edges a few times. They also find a more efficient way to compute the rejection probabilities. In particular, their algorithm generates  d-regular graphs with $d = o(n^{1/2})$ in expected time $O(d^4 + dn)$. In this talk, we build on these ideas providing an algorithm for generating graphs with irregular degrees in expected linear time.
 

Christian Scheideler

Title: The Effect of Faults on Network Expansion
Abstract: I will consider the problem of how resilient networks are to node faults. Specifically, I will investi-
gate the question of how many faults a network can sustain and still contain a large (i.e., linear-sized)
connected component with approximately the same expansion as the original fault-free network. For
adversarial faults, I show that for every network with expansion alpha a large connected component with
basically the same expansion as the original network exists for up to O(alpha*n) faults, which is tight.
Unlike the adversarial case, the expansion of a graph gives a very weak bound on its resilience to random
faults. Thus, I will introduce a different parameter, called the span of a graph, which provides more
precise results on the resilience of a network to random faults.
This is joint work with Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, and David Eppstein

Fiona Skerman

Title: Community detection and the overlap gap property
Abstract: We study the theoretical limits of local algorithms based on the modularity score to recover planted
communities in random graphs. The modularity score qA(G) gives a measure of how well the vertex
partition A divides the graph G into ‘communities’; and is central to the most popular algorithms used
to cluster real network data. We consider recovery in the Stochastic Block Model (SBM) where the graph
G has a planted k-block partition where vertices within the same block connect with probability p while
vertices in different blocks connect with probability q, independently across pairs of vertices. The overlap
gap property (OGP) is a statement about the geometry of near-optimal solutions. We establish that
modularity exhibits OGP on the SBM. This rules out recovery in the SBM by a class of local algorithms
based on the modularity score and shows slow mixing time for a related Markov Chain. Theoretically
this is one of the few instances where OGP has been established on a ‘planted’ rather than ‘null’ model.
Joint work with Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel
Pralat and Yasmin Tousinejad.

Dan Vilenchik

Title: From Local Messages to Global Reasoning: What Do Graph Neural Networks Really Learn in
Combinatorial Optimization?