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)