We are pleased to announce a Workshop on Graphs, Networks, Optimization, and Statistical Inference to be held from March 2 to 6, 2026, in Corfu, Greece.

The workshop focuses on the areas of random structures, sampling, learning theory, and complex networks in a broad sense. In the past few decades, the study of random structures has flourished in computer science and combinatorics, shedding light on the barriers that prevent algorithms from performing efficiently on average, and providing a natural framework for modeling evolving networks. The task of sampling lies at the heart of many algorithmic problems, often emerging as a key subroutine in both theoretical and practical applications. In recent years, the rapid development of learning theory and network science has brought renewed attention to these topics. Sampling now plays a central role in inference and optimization tasks, from training probabilistic models to studying dynamics on large networks. Moreover, random structures, apart from serving as intriguing high-dimensional distributions, they are increasingly incorporated into the design of neural networks to minimize bias and enhance robustness. We aim to bring together leading researchers from these communities across Europe to foster fruitful interactions and to spark new collaborations at the interface of combinatorics, probability, and learning theory.

Further information will follow soon.

Speakers:

Sahar Diskin (ETH Zürich)
Charilaos Efthymiou (University of Warwick)
Robert Elsässer (University of Salzburg)
George Giakkoupis (Inria at Rennes University)
Lisa Hartung (Johannes Gutenberg University)
Dan Hefetz (Ariel University)
Nicolas Macris (EPFL)
Frederik Mallmann-Trenn (King’s College)
James Martin (University of Oxford)
Mike Molloy (University of Toronto)
Noela Müller (TU Eindhoven)
Vasileios Nakos (University of Athens)
Seffi Naor (Technion)
Yuval Peled (Hebrew University)
Tomasz Radzik (King’s College)
Malin Rau (Chalmers University)
Christian Scheideler(Paderborn University)
John Sylvester (University of Liverpool)
Martin Wahl (University of Bielefeld)

Schedule:

	Monday	Tuesday	Wednesday	Thursday	Friday
09:30-10:15	Achlioptas	Martin	Müller	Hintze/Scheftelowitsch	Sylvester
10:20-11:05	Naor (online)	Mallmann-Trenn	Hefetz (online)	Radzik	Efthymiou
11:05-11:25	Coffee break	Coffee break	Coffee break	Coffee break	Coffee break
11:25-12:10	Wahl	Diskin	Free	Zakharov
12:15-13:00	Hartung	Molloy (online)		Macris
13:00-13:20	Small break	Small break		Small break
13:20-14:05	Scheideler	Giakkoupis		Elsässer (online)
14:05-17:05	Discussion session	Discussion session		Discussion session

Talks & Abstracts

Monday, March 2

09:30 – 10:15: Dimitris Achlioptas (University of Athens)
Title: t.b.a.
Abstract: t.b.a.

10:20 – 11:05: Seffi Naor (Technion)
Title: Online Algorithms via Linear Formulations & Randomized Rounding 
Abstract: In the last two decades, techniques derived from linear programming theory and randomized rounding have proved to be very useful in the design and analysis of online algorithms and competitive analysis. We will discuss the role of linear formulations in this line of research and show that strengthened formulations can lead to improved competitive factors. The talk will focus on online bipartite matching, paging, and the k-server problem. 

11:25 – 12:10: Martin Wahl (University of Bielefeld)
Title: Statistical analysis of empirical graph Laplacians
Abstract: This talk deals with the analysis of graph Laplacians as spectral approximations of Laplace-Beltrami operators, by combining tools from high-dimensional statistics, geometry and spectral graph theory. We will also explore higher-order generalizations of graph Laplacians (so-called Hodge Laplacians on graphs), which allow to deduce more sophisticated topological information. 

12:15 – 13:00: Lisa Hartung (Johannes Gutenberg University)
Title: t.b.a.
Abstract: t.b.a.

13:20 – 14:05: Christian Scheideler (Paderborn University)
Title: t.b.a.
Abstract: t.b.a.

Tuesday, March 3

09:30 – 10:15: James Martin (University of Oxford)
Title: Matchings, games, and cores in random graphs
Abstract: I will discuss some older and newer ideas about phase
transitions on trees, cores of random graphs, and random matchings.

For suitable families of configuration models, the emergence of a giant
component, or of a giant 3-core, can be related to phase transitions for
Bienaymé-Galton-Watson trees. Similar correspondences relate the
outcome of certain 2-player games played on BGW trees to the
“Karp-Sipser” core (which appears naturally in the context of
algorithms for finding large matchings or independent sets of a graph).

I’ll mention various results which have been obtained recently on the
size of the Karp-Sipser core, and on the maximum-size matching, for the
Erdös-Rényi random graph in various regimes.

Finally I’ll describe how Stein coupling ideas developed by Barbour
and Röllin can be extended to give CLTs for the size of the largest
matching, and for other related statistics, in configuration models with
suitable degree sequences. 

10:20 – 11:05: Frederik Mallmann-Trenn (King's College)
Title: On the Strong Lottery Ticket Hypothesis
Abstract: The strong lottery ticket hypothesis (SLTH) posits that, for
any given target network, a sufficiently large randomly initialized
neural network contains a subnetwork whose input–output behavior can
approximate that target. This viewpoint suggests an alternative
paradigm for model design: rather than adjusting parameters through
training, we can search for effective subnetworks by pruning. In this
talk, I will introduce the SLTH and discuss several pruning
approaches.

11:25 – 12:10: Sahar Diskin (ETH Zürich)
Title: Supercritical percolation
Abstract: We will talk about a new result describing the behaviour of
supercritical percolation. Joint with Easo, Ramanan-Radhakrishnan,
Tassion, and Sudakov.

12:15 – 13:00: Mike Molloy (University of Toronto)
Title: Simultaneous Edge Colouring 
Abstract: G₁ and G₂ are two simple graphs on the same vertex set, each with maximum degree at most Δ. They share some but not all of their edges. We need to colour the edges E(G₁) ∪ E(G₂) such that each of G₁ and G₂ is properly edge-coloured. Cabello asked: Can we always succeed using at most Δ+2 colours? We prove that we can always succeed using at most Δ+o(Δ) colours. We also prove that with three graphs, we can always succeed using (3/2)Δ + o(Δ) colours. We show that the problem on k graphs comes down to a classic problem regarding fractional matchings of intersecting hypergraphs on k vertices. Our proof analyzes a random procedure to colour the graphs, using the Lovász Local Lemma to show that it succeeds with positive probability. Joint work with Simona Boyadzhiyska, Richard Lang, and Allan Lo.

13:20 – 14:05: George Giakkoupis (Inria at Rennes University)
Title: Minority dynamics with few samples 
Abstract: In the Minority protocol for distributed agreement (Becchetti, et al., SODA'24), n agents holding binary opinions sample k random agents in every round, and update their opinion to the less frequent opinion in their sample. This protocol is particularly suitable for the bit-dissemination problem, where an indistinguishable source agent never changes opinion. Becchetti et al showed that, surprisingly and counter-intuitively, the Minority protocol converges to agreement quickly, after a poly-logarithmic number of rounds w.h.p., when the number of samples is k = Omega(sqrt n). On the other hand, Archivio and Vacus (DISC'24) showed that any memory-less protocol using k = O(1) samples is slow, requiring at least near-linear number of rounds. In this talk, I will present a new analysis of the Minority protocol which shows that a poly-logarithmic number of samples k suffices for the protocol to achieve convergence in poly-logarithmic rounds w.h.p. 

Wednesday, March 4

09:30 – 10:15: Noela Müller (TU Eindhoven)
Title: Information-theoretic thresholds for threshold group testing
Abstract: In the Threshold Group Testing (TGT) problem, one aims to exactly recover
a sparse binary vector, using as few tests (or queries) as possible. Each test is applied to a subset of the coordinates
and returns a positive result if the number of ones in that subset meets or
exceeds a specified threshold, and returns a negative result otherwise. We investigate how information-theoretic thresholds of Threshold Group Testing compare to Binary Group Testing, which corresponds to a threshold of one in our setting. Moreover, we analyse the
impact of increasing the threshold on the required number of tests. Our main
contribution is the derivation of explicit information theoretic upper and lower
bounds on the minimum number of non-adaptive tests for item-regular designs.

The talk is based on joint work with Remco van der Hofstad and Connor Riddlesden.

10:20 – 11:05: Dan Hefetz (Ariel University)
Title: The Hamilton cycle space of random graphs
Abstract: The cycle space of a graph G, denoted C(G), is a vector space over F₂, spanned by all incidence vectors of edge-sets of cycles of G. If G has n vertices, then Cₙ(G) denotes the subspace of C(G), spanned by the incidence vectors of Hamilton cycles of G. In this talk we consider the question of whether Cₙ(G) = C(G) holds with high probability, where G is sampled according to various models of random graphs. Based on joint works with Michael Krivelevich.

Afternoon: Free

Thursday, March 5

09:30 – 10:15: Lukas Hintze, Olga Scheftelowitsch (University of Hamburg/TU Dortmund)
Title: Noisy Linear Group Testing: Exact Thresholds and Efficient Algorithms
Abstract: In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective with a constant probability , independent of all other items. In the (over-)idealized noiseless setting, tests are positive exactly if any of the tested items are defective. We study a more realistic model in which observed test results are subject to noise, i.e., tests can display false positive or false negative results with constant positive probabilities. We determine precise constants c such that cn log n tests are required to recover the infection status of every individual for both adaptive and non-adaptive group testing: in the former, the selection of groups to test can depend on previously observed test results, whereas it cannot in the latter. Additionally, for both settings, we provide efficient algorithms that identify all defective items with the optimal amount of tests with high probability. Thus, we completely solve the problem of binary noisy group testing in the studied setting. 

10:20 – 11:05: Tomasz Radzik (King's College)
Title: Discrete incremental voting
Abstract:  We consider a type of pull voting, which we call Discrete Incremental Voting (DIV), suitable for converging on integer opinions. On observing the opinion of a random neighbour, the vertex updates its opinion by increasing or decreasing it by 1 in the direction of the neighbour’s opinion, if different. If initially there are only two adjacent integer opinions, DIV coincides with the simple pull voting.
Let G=(V,E) be a connected non-bipartite n-vertex graph, let l be the absolute second eigenvalue of the spectrum of G (normalised to [-1,1]), let the initial opinions of vertices be chosen from {1, 2, ... , k}, and let c be the initial degree-weighted average opinion. We show that provided k=o(n/log n) and lk=o(1), with high probability the final opinion is c rounded either down or up. We also analyse the convergence time.

11:25 – 12:10: Pavel Zakharov (TU Dortmund)
Title: WalkSAT is linear on random 2-SAT
Abstract: n an influential article Papadimitriou [FOCS 1991] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with n variables in O(n^2) expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (e.g., [Hoos and Stützle 2000]). In the present article we analyse the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [SICOMP 2007], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.

12:15 – 13:00: Nicolas Macris (EPFL)
Title: Insights on memorization vs generalization in diffusion models from
exact asymptotic learning curves for random features score
Abstract: We theoretically investigate the phenomena of generalization and
memorization in diffusion models. Empirical studies suggest that these
phenomena are influenced by model complexity and the size of the
training dataset. In our experiments, we further observe that the number
of noise samples per data sample (m) used during Denoising Score
Matching (DSM) plays a significant and non-trivial role. We capture
these behaviors and shed insights into their mechanisms by deriving
asymptotically precise expressions for test and train errors of DSM
under a simple theoretical setting. The score function is parameterized
by random features neural networks, with the target distribution being
d-dimensional Gaussian. We operate in a regime where the dimension d,
number of data samples n, and number of features p tend to infinity
while keeping the ratios n/d and p/d fixed. By characterizing the test
and train errors, we identify regimes of generalization and memorization
as a function of these ratios and m. Theoretical findings are consistent
with the empirical observations.

13:20 – 14:05: Robert Elsässer (University of Salzburg)
Title: Upper and Lower Bounds for Plurality Consensus in Population Protocols
Abstract: We consider the following problem known as plurality consensus. We are given a population of n nodes (also called agents), where each node is initially assigned one of k possible colors. The objective is for the population to reach a stable configuration in which every node outputs the color that had the largest initial support (i.e., the plurality color).

We focus on algorithms in the population protocol model. Time proceeds in discrete rounds, and in each round a pair of nodes is selected uniformly at random to interact. During an interaction, the two selected nodes update their states according to a deterministic state transition function that depends only on their current states.

In this talk, we present several upper and lower bounds of protocols that can be viewed as variants of the so-called Undecided State Dynamics. First, we concentrate on the classical Undecided State Dynamics that has a running time of O(k log n), and this bound is tight for certain initial configurations. Then, we consider variants of this protocol that can significantly reduce the convergence time at the cost of using a higher state space. 

Friday, March 6

09:30 – 10:15: John Sylvester (University of Liverpool)
Title: Exploration of Random Temporal Graphs 
Abstract: Temporal graphs are dynamic graphs where the edge set can change in each time step, while the vertex set stays the same. The temporal exploration problem (TEXP) asks for a walk in a given temporal graph, where at most one edge is traversed in each time step, all vertices must be visited, and we assume the walker can see all future graphs in the sequence. In this talk we will consider the temporal exploration problem (TEXP) on a model of random temporal graphs which are connected in each time step. It is known that there are n-vertex temporal graphs which are connected in each time step but require Omega(n²) steps to explore, our aim is to understand what happens against a random adversary. In our model an adversary supplies a measure mu supported on a set of (labelled) spanning trees of a static n-vertex graph G, and we obtain a (random) temporal graph by sampling a spanning tree from mu at each time step. We show that, for any pair (mu, G), w.h.p. there is a schedule which explores the corresponding temporal graph in time O(n^{3/2}) and give an example to show this bound is tight. This is joint work with Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, and Viktor Zamaraev.

10:20 – 11:05: Charilaos Efthymiou (University of Warwick)
Title: On sampling Diluted Spin-Glasses with unbounded interactions
Abstract: Spin-glasses are natural Gibbs distributions that have been studied in
theoretical computer science for many decades. Recently, they have been
gaining renewed attention from the community as they emerge naturally in
neural computation and learning, network inference, optimisation, and
many other areas.

We study the problem of efficiently sampling from spin-glass
distributions when the underlying graph is a typical instance of
$\G(n,d/n)$, i.e., the random graph on $n$ vertices such that each edge
appears independently with probability $d/n$, where the expected degree
$d=\Theta(1)$.

Our main focus is on the 2-spin model at inverse temperature $\beta$,
which serves as a prototypical example of a disordered system. We
consider this distribution to be one of the most interesting case of
spin-glasses, and one of the most challenging to analyse, since its
Gaussian couplings give rise to {\em unbounded} interaction between the
sites of the system.

We employ the well-known {\em Glauber dynamics} to sample from the
aforementioned distribution. We show that for the typical instances of
the 2-spin model on $\G(n,d/n)$, the mixing time of the dynamics is
$O\left(n^{\left(1+\frac{4}{\InvlBlockBoundValue}\right)}\right)$, for
any $\beta<\frac{1}{4\sqrt{d}}$.

Our results can also be adapted for the case of spin-glass
distributions where the interactions are bounded. In that respect, we
obtain rapid mixing of Glauber dynamics for the Viana-Bray model on
$\G(n,d/n)$ when $\beta<\frac{1}{4\sqrt{d}}$. This improves on the
current best bound which is $\beta<\frac{0.18}{\sqrt{d}}$.

We utilise stochastic localisation in our analysis, and in particular,
we build and improve on the scheme introduced in [Liu, Mohanty,
Rajaraman and Wu: FOCS 2024]. This is the first time that stochastic
localisation is used for diluted spin-glasses, where both degrees and
interactions can be unbounded.

Our results rely on introducing an elaborate block partition for the
analysis with the stochastic localisation. We deal with the unbounded
interactions by introducing appropriate matrix norms to control the
entropy decay along the localisation path.

This is a joint work with K. Zampetakis 

Suggested restaurant:

Corfu town:

• Rouvas
• Souvlaki mamma
• Ninos
• Brisk

Garitsa:

• Taverna Dimitris
• Avli
• Stou giatrou

Benitses:

• Paxinos

Bus timetable

Corfu City Bus No6 - Benitses

Corfu City Bus - Line 6 (Benitses)

Valid from Monday 3 November 2025

Monday – Friday

From Town	From Benitses
6:30	7:00
7:50	8:25
8:30	9:05
9:30	10:05
10:45	11:25
12:00	12:40
13:00	13:40
13:45	14:25
14:35	15:10
15:15	15:55
15:50	16:25
17:05	17:40
18:20	18:55
19:30	20:05
21:15	21:50
22:40	23:15

Saturday

From Town	From Benitses
6:30	7:05
7:50	8:25
8:30	9:05
9:30	10:05
10:45	11:20
12:00	12:40
13:20	13:55
14:30	15:05
15:45	16:20
17:30	18:05
18:45	19:20
20:15	20:45
22:00	22:30

Sundays & Holidays

From Town	From Benitses
6:30	7:05
7:50	8:25
9:30	10:05
11:15	11:50
13:30	14:05
14:45	15:20
17:00	17:35
19:00	19:35
21:30	22:00

Accommodation

Organisers:

Dimitris Achlioptas (University of Athens)

Petra Berenbrink (University of Hamburg)

Amin Coja-Oghlan (TU Dortmund)

Maurice Rolvien (University of Hamburg)

Olga Schweftelowitsch (TU Dortmund)

Konstantinos Zampetakis (TU Dortmund)