To content
Department of Com­pu­ter Science
ADYN Summerschool 2024

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 Duisburg-Essen)

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:00-10:00

David Doty-1

Andrea Montanari-1

Andrei Bulatov-3

Andrea Montanari-4

David Doty-5

10:00-10:30

coffee break

coffee break

coffee break

coffee break

coffee break

10:30-11:30

David Doty-2

Andrea Montanari-2

Andrei Bulatov-4

Andrea Montanari-5

Anand Srivastav

11:35-12:35

Anita Winter

Daniel Reichman

Andrea Montanari-3

Adrien Schertzer

 

12:40-14:00

Lunch

Lunch

Lunch

Lunch

Lunch / Lunch
Packages

14:00-15:00

Andrei Bulatov-1

David Doty-3

Free
Afternoon

Andrei Bulatov-5

 

15:00-15:30

coffee break

coffee break

coffee break

 

15:30-16:30

Andrei Bulatov-2

David Doty-4

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 Coja-Oghlan (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 e-mail.

 

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 s-t 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 polynomial-time randomized approximation scheme (FPRAS) for this problem. Our algorithm combines several techniques including dynamic programming, sampling and self-reduction.

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 NP-hard combinatorial optimization problems.

Despite significant interest, few rigorous results about how well SA approximates NP-hard 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 Sherrington-Kirkpatrick 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átal-Erdő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átal-Erdő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 non-linear 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 grapheme-valued Wright-Fisher 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 grapheme-valued Markov chain converges to a grapheme-valued diffusion as the number of vertices goes to infinity. We show that the grapheme-valued diffusion has a stationary distribution that is linked to the Griffiths-Engen-McCloskey (GEM) distribution.

(joint with Andreas Greven, Frank den Hollander and Anton Klimovsky)