Summerschool on Algorithms, Dynamics, and Information Flow in Networks
Topic and Lectures: This 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

Andrei Bulatov (Simon Fraser University)

David Doty (University of California, Davis)

Andrea Montanari (Stanford University)
Our invited speakers are:
 Weiming Feng (ETH Zürich)
 Daniel Reichman (Worcester Polytechnic Institute)
 Adrien Schertzer (University Bonn)
 Anand Srivastav (Kiel University)
 Anita Winter (University DuisburgEssen)
Date and Time: The summerschool takes place from the 1st July to 5th July 2024. It will start in the morning of the 1st and end at noon on the 5th.
Tentative Schedule:
 Monday  Tuesday  Wednesday  Thursday  Friday 
09:0010:00  David Doty1  Andrea Montanari1  Andrei Bulatov3  Andrea Montanari4  David Doty5 
10:0010:30  coffee break  coffee break  coffee break  coffee break  coffee break 
10:3011:30  David Doty2  Andrea Montanari2  Andrei Bulatov4  Andrea Montanari5  Anand Srivastav 
11:3512:35  Anita Winter  Daniel Reichman  Andrea Montanari3  Adrien Schertzer 

12:4014:00  Lunch  Lunch  Lunch  Lunch  Lunch / Lunch 
14:0015:00  Andrei Bulatov1  David Doty3  Free  Andrei Bulatov5 

15:0015:30  coffee break  coffee break  coffee break 
 
15:3016:30  Andrei Bulatov2  David Doty4  Weiming Feng 
 


 Social event 




 Conference Dinner 
Location: It will take place at "Haus Delecke" at the Möhnesee lake and can be reached via bus from Soest main station.
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 Haus Delecke but of course, any other venue can be booked as well.
Registration:
The registration is closed.
Organisers: Petra Berenbrink (Universität Hamburg), Amin CojaOghlan (TU Dortmund University), Martin Hoefer (Frankfurt University), Lena Krieg (TU Dortmund University), Malin Rau (Universität Hamburg) and Olga Scheftelowitsch (TU Dortmund University).
Contact: Feel free to contact us via email.
Invited Talks
Weiming Feng
Title: An FPRAS for two terminal reliability in directed acyclic graphs
Abstract: Network reliability is one of the first problems studied in counting complexity. In this work, we consider the st reliability in directed acyclic graphs (DAG). Given a DAG G=(V,E), a source node s and a sink node t, if each edge in G fails independently with probability p, the problem asks the probability that s can still reach t in the remaining graph. We give a fully polynomialtime randomized approximation scheme (FPRAS) for this problem. Our algorithm combines several techniques including dynamic programming, sampling and selfreduction.
The talk is based on a joint work with Heng Guo (University of Edinburgh).
Daniel Reichman
Title: Hardness results for Simulated Annealing and Metropolis Process in approximating the independent set problem
Abstract: Simulated Annealing (SA) is a local search heuristic that is widely used to solve NPhard combinatorial optimization problems.
Despite significant interest, few rigorous results about how well SA approximates NPhard optimization problems in polynomial time are known. We prove unconditional limitations on the approximation ratio SA and its fixed temperature version Metropolis process can achieve for the maximum independent set problem in polynomial time.
Our results reveal that SA may fail to find optimal or near optimal solutions even in bipartite graphs and trees, where exact polynomial algorithms are known. Many questions remain open.
Joint work with Zongchen Chen (Buffalo), Dan Mikulincer (MIT) and Alex Wein (UC Davis)
Adrien Scherzer
Title: An iterative construction of the TAP equations with the Stein's method.
Abstract: We propose a new iterative construction of solutions of the classical TAP equations for the SherringtonKirkpatrick model. The algorithm can be started in an arbitrary point, and converges up to the AT line. The analysis relies on a novel treatment of mean field algorithms through Stein’s method. As such, the approach also yields weak convergence of the effective fields at all temperatures towards Gaussians.
Anand Srivastav
Title: Recent Advances in the Maker Breaker Triangle Game
Abstract: The triangle game introduced by Chvátal and Erdős (1978) is one of the old and famous combinatorial games. For n, q ∈ N, the (n,q)triangle game is played by two players, called Maker and Breaker, on the complete graph K_n .
Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle. Otherwise Breaker wins. Chvátal and Erdős (1978) proved
that for q < sqrt(n/2), Maker has a winning strategy, while for q > 2 sqrt(n), Breaker wins. So, the threshold bias must be in the interval [sqrt(1/2)sqrt(n) , 2 sqrt(n)]. Since then, the problem of finding the exact constant (and an associated Breaker strategy) for the threshold bias of the triangle game has been one of the interesting open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the ChvátalErdős constant for Breaker’s winning strategy from 2 to 1.935 with a randomized approach. Thereafter, no progress was made. In this work, we present a new deterministic strategy for Breaker leading to his win if q > sqrt(8/3) sqrt(n), for sufficiently large n. This almost matches the ChvátalErdős bound of sqrt(1/2)sqrt(n) for Maker's win (Glazik, Srivastav, Europ.J.Comb.2022). In contrast to previous (greedy) strategies, we introduce a suitable nonlinear potential function on the set of nodes. By keeping the potential small, Breaker picks edges that neutralize the most ‘dangerous’ nodes with incident Maker edges blocking Maker triangles. A characteristic property of the dynamics of the game is that the total potential is not monotone decreasing. In fact, the total potential of the game may increase, even for several turns, but finally Breaker’s strategy prevents the total potential of the game from exceeding a critical level, which results in Breaker’s win. We further survey recent results for cycles of length k, and a general potential function theorem (Sowa, Srivastav 2023).
This is joint work with Christian Glazik, Christian Schielke and Mathias Sowa, Kiel University.
Anita Winter
Title: The graphemevalued WrightFisher diffusion
Abstract: In Athreyaden, Hollander and Roellin( 2021), models from population genetics were used to define stochastic dynamics in the space of graphons arising as continuum limits of dense graphs. In this lecture we give an example of a simple neutral population genetics model for which this dynamics is a Markovian diffusion that can be characterised as the solution of a martingale problem. In particular, we consider a Markov chain in the space of finite graphs that comes from the finite alleles model. We encode the finite graphs as graphemes, which can be represented as a triple consisting of a vertex set (or more generally, a topological space), an adjacency matrix, and a sampling (Borel) measure. We equip the space of graphons with convergence of sample subgraph densities and show that the graphemevalued Markov chain converges to a graphemevalued diffusion as the number of vertices goes to infinity. We show that the graphemevalued diffusion has a stationary distribution that is linked to the GriffithsEngenMcCloskey (GEM) distribution.
(joint with Andreas Greven, Frank den Hollander and Anton Klimovsky)