Prophet Inequalities: Old and New (Correa) 

In this talk, I will survey some of the most widely used techniques for designing and analyzing online algorithms under stochastic input. The playground is that of the classic prophet inequality. This states that, when faced with a finite sequence of non-negative independent random variables, a gambler who knows their distribution and is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest one.

We will begin by reviewing the classic "balanced prices" proof of this result, due to Samuel Cahn. We then introduce the online contention-resolution schemes of Feldman, Svensson, and Zenklusen and discuss how to adapt them to the prophet inequality setting. To wrap up, we dive into the data-driven approach recently introduced by Rubinstein, Wang, andWeinberg. In all cases, we provide additional references to the literature and discuss recent research and open problems. In the final part of the talk, we introduce a new technique to tackle prophet inequalities based on Ordinary Differential Equations and show how this approach provides a unified view of the problem and all known algorithms for it. 

Online Proportional Apportionment (Griesbach) 

Traditionally, the problem of apportioning the seats of a legislative body has been viewed as a one-shot process with no dynamic considerations. While this approach is reasonable for some instances of the problem, dynamic aspects play an important role in many others. In this paper, we initiate the study of apportionment problems in an online setting. Specifically, we introduce an online algorithmic framework to handle proportional apportionment with no information about future events. In this model, time is discrete and there are n parties that receive a certain share of the votes at each time step. An online algorithm needs to irrevocably assign a prescribed number of seats at each time, ensuring that each party receives its fractional share rounded up or down, and that the cumulative number of seats allocated to each party remains close to its cumulative share up to that time.

We consider deterministic and randomized online apportionment methods. For deterministic methods, we construct a family of adversarial instances that yield a lower bound, linear in n, on the worst-case deviation between the seats allocated to a party and its cumulative share. We show that this bound is best possible and is matched by a natural greedy method.

As a consequence, a method guaranteeing that the cumulative number of seats assigned to each party up to any step equals its cumulative share rounded up or down (global quota) exists if and only if $n \leq 3$. Then, we turn to randomized allocations and show that, when $n \leq 3$, we can randomize over methods satisfying global quota with the additional guarantee that each party receives, in expectation, its proportional share in every step.

Our proof is constructive: We show that any method satisfying these properties can be obtained from a flow on a recursively constructed network. We showcase the applicability of our results to obtain approximate solutions in the context of online dependent rounding procedures for multidimensional instances. This is joint work with Javier Cembrano, Jose Correa, and Victor Verdugo.

Recent Advances in Resource-Constrained and Learning-Based Scheduling (Das) 

In this talk, I will discuss two of our recent results in scheduling theory: (1) precedence-constrained resource scheduling and (2) learning to schedule.

Precedence-constrained resource scheduling is a classical problem in scheduling theory. There are n jobs, where each job takes a certain amount of time to finish and has a resource requirement throughout its execution time. There are also precedence constraints among the jobs. Given a resource budget, the problem asks us to schedule the jobs while obeying the precedence constraints, in order to minimize the makespan, that is, the maximum completion time of any job, such that at any point in time, the total resource used by all jobs is at most the given resource budget. In the offline setting, an important open question is whether a polynomial-time $O(1)$-factor approximation algorithm can be found. We prove an almost tight hardness of approximation: for some constant $(\alpha > 0)$, there is no $o(\log^{\alpha} T_{\max})$-factor approximation algorithm with n jobs of maximum job length $t_{\max}$, unless P = NP.

In the learning-to-schedule problem, we study the fundamental problem of scheduling jobs with stochastic sizes to minimize the total completion time for both single and parallel machines. We explore the problem of efficiently learning to schedule when the job-size distributions are unknown, and we are unable to directly obtain samples from them. We show that, in our learning process, we incur an optimal $\sqrt{T}$ regret over a series of $T$ periods. If we allow a $(1 + \epsilon)$-approximation in the total completion time, then we exponentially improve the regret to $O(\log^3 T)$.

The rank of the random $k$-XORSAT matrix beyond satisfiability (Rolvien) 

We study the rank of the random $k$-XORSAT matrix beyond the satisfiability threshold. In this regime, the matrix fails to have full row rank w.h.p. We derive the precise limiting distribution of the rank, as well as that of the corresponding 2-core matrix. This is ongoing work.

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP (Sokolowski) 

In this talk, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within $O­(m + n^{2−ϵ})$ work and $O­(n^{1−\epsilon})$ depth for some positive $\epsilon > 0$. In particular, for dense graphs with non-negative real weights, we provide the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Our result immediately yields improved strongly polynomial parallel algorithms for min-cost flow and the assignment problem. It also leads to the first non-trivial strongly polynomial dynamic algorithm for minimum mean cycle. Moreover, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights.
Based on SODA 26 publication. 

On Computing Top-k Simple Shortest Paths from a Single Source (D’Emidio) 

We investigate the problem of computing the top-k simple shortest paths in weighted digraphs. While the single-pair variant has been extensively studied over the past decades, with Yen’s algorithm and its heuristic improvements emerging as the most effective solving strategies, relatively little attention has been devoted to the more general single-source version, which asks to determine top-k simple shortest paths from a source vertex to all other vertices. Motivated by the numerous practical applications of ranked shortest paths, in this paper, we provide new insights and algorithmic contributions to this problem. In particular, we first present a characterization of the structural properties of its solutions. Then, we introduce the first polynomial-time algorithm specifically designed to handle it. On the one hand, we prove our new algorithm is on par, in terms of time complexity, with the only polynomial-time approach known to solve the problem, that is, applying the fastest single-pair algorithm independently to each vertex pair formed by the source and the remaining vertices. On the other hand, through an extensive experimental evaluation, we demonstrate that our algorithm outperforms the latter in terms of running time, achieving speed-ups of up to several orders of magnitude. These results establish our new algorithm as the solution to be preferred for computing k simple shortest paths from a single source in practical settings.
Based on ALENEX 26 publication. 

Unsupervised machine learning applied to stochastic optimisation (Ortmann) 

This talk concerns stochastic optimisation models where some quantity is to be maximised or minimised subject to some constraints which are only partially known in advance. One way to model this is to look for the optima value of the expectation of the random quantity. However, it is typically not possible to find closed-form expressions for the expected value, leading to the need of numerical methods. The sample average approximation (SAA) approach uses samples (called scenarios) from the underlying probability measure and uses the empirical mean over these samples to turn the stochastic into a deterministic problem of much larger size. However, in many applications, the number of scenarios required to realistically model the uncertainty typically makes the optimization problem numerically intractable.

I will give an overview on problem-based clustering to extract information about the stochastic program from the single-scenario solutions. In particular, I will introduce  distance matrices on the scenario set that encode the notion of opportunity cost of predicting the wrong scenario. Clustering can then be applied to the scenario set equipped with these distances which leads to approximative feasible solutions as well as performance guarantees in the form of upper and lower bounds. We also obtain interesting new structures on the scenario set.

This talk is based on joint work (ongoing and completed) with Samah Abdalrhaman, Shubhajit Dey, Yuchen Ge, Olivia Harrison, Michael Hewitt, Julian Keutchayan and Walter Rei.

On the Gibbs Uniqueness Threshold of a random k-SAT Instance (Klindworth) 

In theoretical computer science, an important problem is the $\mathrm{SAT}$ problem. Its decision variant asks whether there exists a satisfying assignment $\tau \in \{+,-\}^n$ for a Boolean formula $\Phi : \{+,-\}^n \to \{+,-\}$. A $k$-$\mathrm{SAT}$ formula is a special case of an $\mathrm{SAT}$ formula in which the formula is expressed as a conjunction of finitely many clauses. Each clause is a disjunction of exactly $k$ literals. It is well known that $\mathrm{SAT}$ is $\mathrm{NP}$-complete. We can define the problems $\#\mathrm{SAT}$ and $\#k\text{-}\mathrm{SAT}$, which ask for the number of satisfying assignments of an $\mathrm{SAT}$ or $k$-$\mathrm{SAT}$ formula $\Phi$.

There is an approach to compute the number of satisfying assignments $Z(\Phi)$, for a randomly generated $k$-$\mathrm{SAT}$ formula with $n$ variables. First, a variable degree parameter $d \in \mathbb{R}_\geq 0$ is fixed. The number of clauses is then drawn from a  Poisson distribution with mean $dn/k$. Each clause is generated independently by selecting $k$ variables uniformly at random from the set of $n$ variables, and assigning each literal a sign independently and uniformly from $\{+,-\}$.

For the case $k=2$, this problem is well analyzed. There exists a threshold $d_\text{uniq} = 2$ for the variable degree $d$, known as the \emph{Gibbs uniqueness} threshold. Below this threshold, the typical number of solutions can be computed, that is, the limit $\lim_{n \to \infty} \frac{1}{n}\log Z(\pmb{\Phi})$ for a random 2-$\mathrm{SAT}$ formula $\pmb{\Phi}$.

However, for $k \geq 3$ the exact value of the Gibbs uniqueness threshold, remains an open problem.

We employ an approach known as belief propagation to construct an operator that converges to a distribution from which the number of solutions can be estimated. We will show that if the expectation of this distribution equals $1/2$, a property known as Gibbs uniqueness holds. Consequently, this operator can be used to approximate the Gibbs uniqueness threshold for a given $k$. Moreover, for specified values of $k$ and $d$, it allows us to estimate the expected number of solutions of a random $k$-$\mathrm{SAT}$ formula.

Approximating Matroid Basis Testing for Partition Methods using Budget-In-Expectation (Schewior) 

We consider the following Stochastic Boolean Function Evaluation problem, which is closely related to several problems from the literature. A matroid $\mathcal{M}$ (in compact representation) on ground set $E$ is given, and each element $i\in E$ is active independently with known probability $p_i\in(0,1)$. The elements can be queried, upon which it is revealed whether the respective element is active or not. The goal is to find an adaptive querying strategy for determining whether there is a basis of $\mathcal{M}$ in which all elements are active, with the objective of minimizing the expected number of queries.

When $\mathcal{M}$ is a uniform matroid, this is the problem of evaluating a $k$-of-$n$ function, first studied in the 1970s. This problem is well-understood, and has an optimal adaptive strategy that can be computed in polynomial time. Taking $\mathcal{M}$ to instead be a partition matroid, we show that previous approaches fail to give a constant-factor approximation. Our main result is a polynomial-time constant-factor approximation algorithm producing a randomized strategy for this partition matroid problem. We obtain this result by combining a new technique with several well-established techniques. Our algorithm adaptively interleaves solutions to several instances of a novel type of stochastic querying problem, with a constraint on the \emph{expected} cost. We believe that this type of problem is of independent interest, will spark follow-up work, and has the potential for additional applications.

This is joint work with Lisa Hellerstein und Benedikt Plank

Dynamic Debt Swapping in Financial Networks (Wilhelmi) 

A debt swap is an elementary edge swap in a directed, weighted graph, where two edges with the same weight swap their targets. Debt swaps are a natural and appealing operation in financial networks, in which nodes are banks and edges represent debt contracts. They can improve the clearing payments and the stability of these networks. However, their algorithmic properties are not well-understood.

We analyze the computational complexity of debt swapping. Our main interest lies in semi-positive swaps, in which no creditor strictly suffers and at least one strictly profits. These swaps lead to a Pareto-improvement in the entire network. We consider network optimization via sequences of v-improving debt swaps from which a given bank v strictly profits. For ranking-based clearing, we show that every sequence of semi-positive v-improving swaps has polynomial length. In contrast, for arbitrary v-improving swaps, the problem of reaching a network configuration that allows no further swaps is PLS-complete.

We study reachability problems -- deciding if a sequence of swaps exists between given initial and final networks. We design a polynomial-time algorithm for arbitrary swaps and derive complexity results for multiple other types of swaps.

In global optimization, the goal is to maximize the utility of a given bank v by performing a sequence of debt swaps in the network. This problem is NP-hard to approximate for multiple types of swaps. Many of our results can be extended to networks with arbitrary monotone clearing.

The Strong Lottery Tickets Hypothesis and the Random Subset Sum Problem (Mallmann-Trenn)

The Strong Lottery Ticket Hypothesis (SLTH) challenges the necessity of weight updates in training neural networks. It posits that sufficiently large random neural networks already contain sparse subnetworks capable of approximating any target network of smaller size—without requiring any further weight training. In this talk, I will explore the SLTH as a theoretical framework that reimagines the role of initialization in deep learning. Building on this foundation, I will connect the SLTH to the Random Subset Sum Problem, a well-studied NP-hard problem in combinatorial optimization. By framing the search for these high-performing sparse subnetworks as a variant of the Random Subset Sum Problem, we can leverage insights from theoretical computer science to understand the likelihood of such subnetworks existing.

The Voter Model with Opinion Graph (Götte) 

The Deffuant-Weisbuch (DW) process is a classic approach to analyze opinion formation. In this process, each agent $u$ has a numeric opinion $x_u$. In each step, a pair of agents chosen uniformly at random are selected for an update. If their current opinions are within a confidence bound of $\varepsilon > 0$, they both shift their opinion by the same distance towards each other. Otherwise, they retain their current opinion values.

We study the impact of discrete opinions on this process. For a chosen pair of agents, we assume one of the agents (chosen uniformly at random) adopts the opinion of the other. Our scenario represents a generalization of the (pull) voter model, which we call the voter model with opinion graph. Opinions are nodes in an undirected opinion graph $G$. In each step, an agent $u$ samples another agent $v$. $u$ adopts the opinion $x_v$ if and only if $x_v$ and $x_u$ are neighbors in $G$.

Our results bound the convergence time for several variants of this pull process in the voter model with opinion graph. In general, the convergence time is always at most $\tilde{O}(n^2)$, i.e., in the same order of magnitude as for the standard voter model. As our main result, for instances with bounded opinion degree and good initial opinion distribution among the agents, we prove that the convergence time can become as low as $\tilde{O}(n)$. When only pairs of agents with neighboring opinions are chosen in each step, the convergence time becomes $\tilde{O}(\text{poly}(\Delta,\hat{s}) \cdot n)$, where $\Delta$ is the maximum degree in the opinion graph and $\hat{s}$ the maximum number of agents on any opinion in the beginning. 

Sampling Colorings with Markov Chains (Carlson)

Graph coloring is a fundamental problem at the intersection of computer science and mathematics. A graph is k-colorable if its vertices can be assigned k colors such that adjacent vertices receive different colors. The problems of finding or sampling such colorings play crucial roles in both theoretical and practical research; they serve as natural test beds for algorithm design techniques and arise in many engineering applications. While a simple greedy algorithm can efficiently find a (d+1)-coloring for a graph with maximum degree d, the problem of uniformly sampling such a coloring is significantly more challenging. A well-known conjecture states that it is possible to efficiently sample a (d+2)-coloring.

In this talk, we will explore the importance of sampling random colorings and the history of using Markov chains to address this conjecture. Our discussion will include a review of the recent breakthrough by Carlson and Vigoda, which demonstrates the rapid mixing of Flip dynamics and the existence of an efficient algorithm for sampling colorings when k > 1.809*d. Along the way, we will introduce key concepts such as Glauber dynamics, path coupling, and Flip dynamics. We conclude with a discussion of open problems and future research directions for sampling colorings and analyzing similar Markov chains.

Belief Propagation Guided Decimation on Random k-XORSAT (Chatterjee)

We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random k-XORSAT problem. Specifically, we derive an explicit threshold up to which the algorithm succeeds with a strictly positive probability Ω(1) that we compute explicitly, but beyond which the algorithm with high probability fails to find a satisfying assignment. In addition, we analyse a thought experiment called the decimation process for which we identify a (non-)reconstruction and a condensation phase transition. The main results of the present work confirm physics predictions from [Ricci-Tersenghi and Semerjian: J. Stat. Mech. 2009] that link the phase transitions of the decimation process with the performance of the algorithm, and improve over partial results from a recent article [Yung: Proc. ICALP 2024]. 

The Offended Voter Model (Seiler)

In this talk we discuss a variant of the voter model on a coevolving network in which interactions of two individuals with differing opinions only lead to an agreement on one of these opinions with a fixed probability q. Otherwise, with probability 1-q, both individuals become offended in the sense that they never interact again, i.e. the corresponding edge is removed from the underlying network.  Eventually, these dynamics reach an absorbing state at which there is only one opinion present in each connected component of the network. If globally both opinions are present at absorption we speak of "segregation", otherwise of "consensus'".  

We show that segregation and a weaker form of consensus both occur with positive probability for every q ∈ (0,1) and that the segregation probability tends to 1 as q → 0. Furthermore, we establish that, if q → 1 fast enough, with high probability the population reaches consensus while the underlying network is still densely connected.  We briefly discuss results from simulations to assess the obtained results and to discuss further research directions.  

This talk is based on joint work with Raphael Eichhorn and Felix Hermann.

Designing Exploration Contracts (Schecker)

We propose a new model for contract design with sequential decision making where a principal delegates a search task to an agent. The agent sequentially explores n boxes, suffers an exploration cost for each inspected box, and selects the content (the "prize") of one inspected box as outcome. Agent and principal each obtain a value from the selected prize.

To influence the search, the principal designs a contract with a non-negative payment to the agent for each potential prize. Her goal is to maximize her value minus payment. This natural contract scenario shares close relations to the classic Pandora's Box problem. We show how to compute optimal linear contracts in polynomial time. Moreover, we obtain efficient algorithms for optimal general contracts in several cases: When the agent has no individual value for prizes, when each box has only one prize with non-zero value for principal and agent, or for i.i.d. boxes with a single prize with positive value for the principal.  

This is joint work with Martin Hoefer and Kevin Schewior.

Prophet Inequalities with Minimal Priors (Reiffenhäuser)

Prophet Inequalities are a well-established paradigm in online optimization, but require knowledge of exact prior distributions. The talk will introduce and give an overview on some results that instead run on only a single sample per distribution, still achieving comparable, constant ratios.

Persuading Agents in Opinion Formation Games (Koglin)

Prominent opinion formation models such as the one by Friedkin and Johnsen (FJ) concentrate on the effects of peer pressure on public opinions. In practice, opinion formation is also based on information about the state of the world and persuasion efforts. In this talk, we will present an approach of Bayesian persuasion in the FJ model. There is an unknown state of the world that influences the internal beliefs of n agents. A sender S can (partially) reveal information about the state to all agents. The agents update their internal beliefs, and an equilibrium of public opinions emerges. We propose algorithms for the sender to reveal information in order to optimize various aspects of the emerging equilibrium.

We will focus on a general class of range-based objectives based on desired opinion ranges for each agent. We will present efficient algorithms for the case that the matrix of internal beliefs in all states has constant rank. This generalizes, e.g., instances with a constant number of states and/or agents.

This is joint work with Martin Hoefer and Tolga Tel.

Constraint Satisfaction Problems with Advice (Ghoshal)

We initiate the study of algorithms for Constraint Satisfaction Problems (CSPs) with ML oracle advice. We introduce two models of advice and then design approximation algorithms for several fundamental CSPs, such as Max Cut, Max 2-Lin, and Max 3-Lin in these models. In particular, we show the following.  

1.  For Max-Cut and Max 2-Lin, we design an algorithm that yields near-optimal solutions when the average degree is larger than a threshold degree, which only depends on the amount of advice and is independent of the instance size. We also give an algorithm for nearly satisfiable Max 3-Lin instances with quantitatively similar guarantees.  

2. Further, we provide impossibility results for algorithms in these models. In particular, under standard complexity assumptions, we show that Max 3-Lin is still $1/2 + \eta$ hard to approximate given access to advice, when there are no assumptions on the instance degree distribution. Additionally, we also show that Max 4-Lin is $1/2 + \eta$ hard to approximate even when the average degree of the instance is linear in the number of variables.

This is joint work with Konstantin Makarychev and Yury Makarychev.

A Combinatorial Approach to Chernoff Bounds (Kuszmaul)

The Chernoff bound is one of the most widely used tools in theoretical computer science. It's rare to find a randomized algorithm that doesn't employ a Chernoff bound in its analysis. The standard proofs of Chernoff bounds are beautiful but in some ways not very intuitive. In this paper, I'll show you a different proof that has four features: (1) the proof offers a strong intuition for why Chernoff bounds look the way that they do; (2) the proof is user-friendly and (almost) algebra-free; (3) the proof comes with matching lower bounds, up to constant factors in the exponent; and (4) the proof extends to establish generalizations of Chernoff bounds in other settings. The ultimate goal is that, once you know this proof (and with a bit of practice), you should be able to confidently reason about Chernoff-style bounds in your head, extending them to other settings, and convincing yourself that the bounds you're obtaining are tight (up to constant factors in the exponent).

Naively Sorting Evolving Data is Optimal and Robust (Giakkoupis)

In the evolving sorting problem, introduced by Anagnostopoulos, Kumar, Mahdian and Upfal (2011), the true ranking changes while the sorting algorithm is processing the input. More precisely, each comparison operation of the algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the true rank of a random item by a "small" random value. The goal is to maintain an ordering that remains close to the true ranking over time.  I will present a very simple sorting algorithm, which samples a random pair of adjacent items in each step and swaps them if they are out of order.  The algorithm achieves and maintains, with high probability, optimal total deviation, O(n), and optimal maximum deviation, O(logn), under very general model assumptions.  

G. Giakkoupis, M. Kiwi and D. Los. Naively sorting evolving data is optimal and robust. Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 2217-2242, 2024.  

Fast Self-Stabilizing Ranking (Götte)

We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given $n$ anonymous agents, and the goal is to assign each agent a unique rank in $\{1, \dots, n\}$. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well. Ranking requires at least $n$ states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only $n + O(\log n)$ states. Our protocol stabilizes in $O(n^2\ log n)$ interactions w.h.p. and in expectation, using $n + O(\log^2 n)$ states in total. Our stabilization time is asymptotically optimal. In comparison to the currently best known ranking protocol by Burman et al. [PODC ‘21], which requires $n + \Omega(n)$ states, our result exponentially improves the number of overhead states. 

A New Look on an Old Counter Example of Doeblin Measures (Steiger)

We consider an example from 2017 of a Doeblin function that admits two extremal Doeblin measures, and see that's variants thereof provide counter examples to a number of conjectures, in particular we get a non-mixing Doeblin measure, and Doeblin functions that admit Doeblin measures of different entropies. I will start by giving a thorough introduction to the topic of Doeblin functions and measures. Based on an old work with Hoffman and Sidoravicius, and a new work with Conache, Johansson and Öberg.

Noisy Linear Group Testing: Exact Thresholds and Efficient Algorithms (Scheftelowitsch)

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 cnlogn 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.

Chromatic Number of Randomly Augmented Graphs (Srivastav)

An extension of the Erdős-Renyi random graph model $G_{n,p}$ is the model of perturbed graphs introduced by Bohman, Frieze and Martin (2003). This is a special case of the randomly augmented graphs studied in this paper. An augmented graph is the union of a deterministic host graph and a random graph. Among the first problems in perturbed graphs has been the question how many random edges are needed to ensure Hamiltonicity of the graph. This question was answered in the paper by Bohman, Frieze and Martin. The host graph is often chosen to be a dense graph. In recent years several papers on combinatorial functions of perturbed graphs were published, e.g. on the emergence of powers of Hamiltonian cycles (Dudek, Reiher, Ruciński, Schacht 2020), the properties of Positional Games played on perturbed graphs (Clemens, Hamann, Mogge, Parczyk, 2020) and the emergence of multiple invariants e.g. fixed clique size (Bohman, Frieze, Krivelevich, Martin, 2004).

In this paper we study the chromatic number of randomly augmented graphs. We concentrate on a host graph $H$ with chromatic number $o(n)$, augmented by a $G_{n,p}$ with $n^{-\frac{1}{3} + \delta}\leq p(n) \leq 1-\delta$ for some $\delta \in (0,1)$. We denote such a graph by $\pert_{H,p}$. Our main result is an upper bound for the chromatic number of such a randomly augmented graph $\pert_{H,p}: we show that for any $\epsilon>0$ there is a $n(\epsilon) \in \N$ such that for $n \geq n(\epsilon)$ with high probability $\chromaticOf{\pert_{H,p}} \leq (1+o(1)) \cdot \frac{n \log(b)}{2 (\log(n) - \log(\chromaticOf{H}))}$. This result collapses to the famous theorem of Bollobás (1988), when $H$ is the empty host graph, thus our result can be regarded as a generalization of the latter. Our proof is not constructive. To give the reader an impression of a coloring strategy, we give a constructive proof of the upper bound for the chromatic number of $\pert_{H,p}$ where the chromatic number of the host grah is at most $\frac{n}{\log(n)^{\alpha}}$ where $\alpha>\frac{1}{2}$.

Insights into (k, ρ)-Shortcutting Algorithms (Leonhardt)

A graph is called a (k, ρ)-graph iff every node can reach ρ of its nearest neighbors in at most k hops. This property has proven useful in the analysis and design of parallel shortest-path algorithms [Blelloch et al., 2016; Dong et al., 2021]. Any graph can be transformed into a (k, ρ)-graph by adding shortcuts. Formally, the (k,ρ)-Minimum-Shortcut-Problem (kρ-MSP) asks to find an appropriate shortcut set of minimal cardinality. We show that kρ-MSP is NP-complete in the practical regime of k ≥ 3 and ρ = Θ(n^ε) for ε > 0. With a related construction, we bound the approximation factor of known kρ-MSP heuristics [Blelloch et al., 2016] from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) that optimally solves kρ-MSP. Finally, we compare the practical performance and quality of all algorithms empirically.

This is joint work with Manuel Penschuck and Ulrich Meyer.

A Strongly Polynomial Algorithm for The Minimum-cost Generalize Flow Problem (Végh)

We give a strongly polynomial algorithm for minimum cost generalized flow and, as a consequence, for all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem.

Our approach is based on the recent ‘subspace layered least squares’ interior point method, an earlier joint work with Allamigeon, Dadush, Loho and Natura. They show that the number of iterations needed by the IPM can be bounded in terms of the `straight line complexity’ of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. Our main contribution is a combinatorial analysis showing that the straight-line complexity of any minimum cost generalised flow instance is polynomial in the number of arcs and vertices.

This is joint work with Daniel Dadush, Zhuan Khye Koh, Bento Natura, and Neil Olver.

Claims Trading with Default Costs (Huth)

In the Eisenberg-Noe model, a model for debt between financial institutions and quantifying systemic risk, there are n banks represented by nodes in a directed graph. Directed edges represent debt claims, and edge weights are liabilities. Each bank can use incoming payments to clear its debt. Moreover, each bank has a non-negative amount of external assets, which can also be used for payment of claims. With this talk, I will convey basic intuitions for problems in the model, specifically claims trades. In claims trades, there is a bank v in distress and a trading partner w. The latter is taking over some claims of v and in return giving liquidity to v. The idea is to rescue v (or mitigate contagion effects from v’s insolvency). We focus on the impact of trading claims fractionally, i.e. when v and w can agree to trade only part of a claim. This is joint work with Martin Hoefer and Lisa Wilhelmi.

Recent Advances in Engineering Dynamic Graph Algorithms (Schulz)

In recent years, the field of fully dynamic algorithms has seen remarkable theoretical progress. However, from a practical standpoint, these advancements have received relatively little attention. Few of these algorithms have been implemented or evaluated on real-world datasets, leaving their practical viability largely unexplored.

In this talk, we provide a concise overview of our recent work in the engineering of dynamic graph algorithms. We focus on several key problems such as weighted matching, weighted independent sets and edge orientation. For each problem, we discuss the performance of dynamic algorithms, highlighting their strengths and practical potential. Lastly, we aim to raise awareness of our recently published survey.

Distributed Graph Algorithms with Predictions (Ellen)

Algorithms with predictions are algorithms that are given extra information about a problem, which may be incorrect. The better the prediction, the more it should help for solving the problem. I will present a framework for evaluating deterministic distributed graph algorithms with predictions, some templates for transforming algorithms in synchronous message passing systems to effectively make use of predictions, and apply them to obtain good distributed algorithms with predictions for the Maximal Independent Set problem.

Improved Bounds for Discrete Incremental Voting (Götte)

Pull voting is a well-known and well-understood random process in which vertices of a connected graph have initial opinions chosen from a set of $k$ distinct opinions. At each step, a random vertex alters its opinion to that of a randomly chosen neighbor. However, in many real-world contexts, it seems unrealistic that anyone would unconditionally change their opinion to that of a random neighbor based only on observing that  one neighbor in a one-off operation, and in particular, regardless of the extent to which those two opinions differ.

In this talk, we present and provide new results for the discrete incremental voting process (DIV) introduced by Cooper, Radzik, and Shiraga [OPODIS '23] on graphs of bounded expansion. In this variant of a pull voting process, we also consider a set $V$ of $n$ vertices connected in an undirected graph $G = (V, E)$ where each vertex has an integer opinion. In contrast to classical voting, whenever two neighboring vertices interact, \textbf{either} the vertex with a larger opinion decreases its opinion by $1$, \textbf{or} the vertex with a lower opinion increases by $1$. This process must also converge to a unique opinion that depends on the vertices (initial) average opinion.

We give a general bound on the convergence time for DIV on graphs of bounded expansion. Suppose the graph has expansion $\Phi$ and the maximal difference between opinions is $\kappa$. Then, the expected convergence time is $O\left(\frac{\kappa\cdot n + n^2}{\Phi^2}\right)$. Our bound is existentially optimal for a large class of graphs of bounded expansion.

The 2-norm Case (Efthymiou)

In this work, we establish novel, optimum mixing results for the Glauber dynamics on the Hard-core and Ising models using the powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020]. The  mixing bounds are expressed in terms of matrix norms of the underlying graph G rather than the maximum degree Δ. We obtain one set of results with the mixing bounds expressed in terms of ||A||_2, where A is the adjacency matrix. These results improve on the seminal work in [Hayes: FOCS 2006].

In a second set of results, we obtain, for the first time, mixing bounds that are expressed in terms of ||H^N||^(1/N)_2  where H is the Hashimoto non-backtracking matrix, while we can choose N to be any bounded integer. Even though the results with the non-backtracking matrix are interesting in their own right, they have some interesting consequences:
(a) they include the max degree mixing bounds as a special case,
(b) they allow us to refine the celebrated connection between the hardness of approximate counting and the phase transitions from statistical physics,
(c) for locally tree-like graphs, they imply rapid mixing bounds expressed in terms of the local connective constant.

We obtain all the above by proposing a novel  analysis to bound the maximum eigenvalue of I^(Λ,τ), which yields more accurate estimations than earlier works.

On Sampling Diluted Spin-Glasses Using Glauber Dynamics  (Zambetakis)

We consider the 2-spin model at inverse temperature \beta when the underlying graph is an instance of G(n,d/n), where the expected degree d=\Theta(1). We study the problem of efficiently sampling from the aforementioned distribution using the well-known Markov chain called Glauber dynamics.   For a range of \beta, depending only on d, and for typical instances of the 2-spin model on G(n,d/n), we show that the corresponding (single-site) Glauber dynamics exhibits mixing time O(n^{2+3/log^2 d}). The range of \beta for which we obtain our rapid mixing result, corresponds to the expected influence being smaller than 1/d.   We establish our results utilising the well-known path-coupling technique. In the standard setting of Glauber dynamics on G(n,d/n), one has to deal with the so-called effect of high degree vertices. Here, with the spin-glasses, rather than considering vertex-degrees, it is natural to use a different measure on the vertices of the graph, that we call aggregate influence.

Two Stories about Distortion in Social Choice (Caragiannis)

The notion of distortion has received much attention in recent years by the computational social choice community. In general, distortion quantifies how the lack of complete information affects the quality of the social choice outcome. Ideally, a distortion of 1 means that the social choice outcome is the most efficient one.

In the talk, we will consider two related scenarios. The first one is inspired by voting under the impartial culture assumption. We assume that agents have random values for the alternatives, drawn from a probability distribution independently for every agent-alternative pair. We explore voting rules that use a limited number of queries per agent in addition to the agent's ordinal information. For simple distributions, we present rules that always select an alternative of social welfare that is only a constant factor away from the optimal social welfare (i.e., rules of constant distortion).    

The second scenario is motivated by the practice of sortition. Here, we assume that agents correspond to points on a metric space. Our objective is to select, in a fair manner, a subset of the agents (corresponding to a citizens' assembly) so that for every election with alternatives from the same metric space, the most preferred alternative of the citizens' assembly has a social cost that is very close to that of the optimal alternative for the whole agent population. Our positive results indicate that assemblies of size logarithmic in the number of alternatives are sufficient to get constant distortion in this model.

The talk is based on two papers that are joint works with Karl Fehrs, and with Evi Micha and Jannik Peters, respectively.

Algorithms for Claims Trading (Wilhelmi)

The recent banking crisis has again emphasized the importance of understanding and mitigating systemic risk in financial networks. In this paper, we study a market-driven approach to rescue a bank in distress based on the idea of claims trading, a notion defined in Chapter 11 of the U.S. Bankruptcy Code. We formalize the idea in the context of the seminal model of financial networks by Eisenberg and Noe. For two given banks v and w, we consider the operation that w takes over some claims of v and in return gives liquidity to v (or creditors of v) to ultimately rescue v (or mitigate contagion effects). We study the structural properties and computational complexity of decision and optimization problems for several variants of claims trading.

When trading incoming edges of v (i.e., claims for which v is the creditor), we show that there is no trade in which both banks v and w strictly improve their assets. We therefore consider creditor-positive trades, in which v profits strictly and w remains indifferent. For a given set C of incoming edges of v, we provide an efficient algorithm to compute payments by w that result in a creditor-positive trade and maximal assets of v. When the set C must also be chosen, the problem becomes weakly NP-hard. Our main result here is a bicriteria FPTAS to compute an approximate trade, which allows for slightly increased payments by w. The approximate trade results in nearly the optimal amount of assets of v in any exact trade. Our results extend to the case in which banks use general monotone payment functions to settle their debt and the emerging clearing state can be computed efficiently. 

Robust Graph Alignment: Evaluation and Enhancements (Mottin)

In this talk, we shed some light on the generalization abilities of graph neural networks (GNNs) in various settings. First, we establish a tight connection between the 1-dimensional Weisfeiler-Leman algorithm and the VC dimension of GNNs. Graph alignment is the problem of establishing correspondences among the nodes of two graphs. This problem finds applications across divers domains, such as ego-network analysis, protein alignment, and social networks. Despite its apparent simplicity, achieving robust and accurate alignments remains a challenge, particularly in the presence of noise.

In this talk, I present a comprehensive evaluation of graph alignment methods, shedding light on the efficacy of existing approaches and the conditions under which they perform well. Our evaluation reveals that many methods are susceptible to even modest levels of noise, prompting the need for more robust solutions. Surprisingly, our findings demonstrate that simple baseline methods, when appropriately tuned, can yield competitive and sometimes superior results compared to more complex algorithms.

Building upon these insights, we introduce novel contributions aimed at enhancing the robustness of graph alignment methodologies. First, we propose leveraging spectral methods to filter out noise from the adjacency matrix, thereby improving the signal-to-noise ratio and enhancing alignment accuracy. Second, we tease on the effectiveness of regularization techniques in refining alignment objectives, mitigating the impact of noise and uncertainties in the alignment process. By amalgamating empirical evaluations with innovative enhancements, this talk offers a roadmap towards achieving robust graph alignments and paves the way to possible new collaborations between theory and practice. 

Uniform Generation of Temporal Graphs with Given Degrees (Allendorf)

Uniform sampling from the set G(d) of graphs with a given degree-sequence d = (d_1, ..., d_n) is a classical problem in the study of random graphs. We consider an analogue for temporal graphs in which the edges are labeled with integer timestamps The input to this generation problem is a tuple D = (d, T) and the task is to output a uniform random sample from the set G(D) of temporal graphs with degree-sequence d and timestamps in the interval [1, T]. By allowing repeated edges with distinct timestamps, G(D) can be non-empty even if G(d) is, and as a consequence, existing algorithms are difficult to apply.

We describe an algorithm for this generation problem which runs in expected linear time O(M) if Delta^{2+eps} = O(M) for some constant eps > 0 and T - \Delta = Omega(T) where M = sum_i d_i and Delta = max_i d_i. Our algorithm applies the switching method of McKay and Wormald to temporal graphs: we first generate a random temporal multigraph and then remove self-loops and duplicated edges with switching operations which rewire the edges in a degree-preserving manner.

Low Diameter Graph Decompositions by Approximate Distance Computation (Lenzen)

In many models for large-scale computation, decomposition of the problem is key to efficient algorithms. For distance-related graph problems, it is often crucial that such a decomposition results in clusters of small diameter, while the probability that an edge is cut by the decomposition scales linearly with the length of the edge. Previous techniques heavily building on single source shortest paths (SSSP) computations, which constitute a complexity bottleneck in many models of computation. Therefore, it is desirable to replace exact SSSP computations with approximate ones. However this imposes a fundamental challenge, since prior constructions inherently rely on the SSSP computation to be exact.

We overcome this obstacle by developing a technique termed blurry ball growing, which allows us to replace exact SSSP computations by (a small number of) approximate ones. The utility of our approach is showcased by deriving efficient algorithms that work in the Congest, PRAM, and semi-streaming models of computation. As an application, we obtain metric tree embedding algorithms in the vein of Bartal (FOCS 96) whose computational complexities in these models are optimal up to polylogarithmic factors. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only O(log n) times, which is of interest for capacitated problems and simulating Congest algorithms on the tree into which the graph is embedded.

A Tight (3/2 + ε)-Approximation Algorithm For Demand Strip Packing (Rau)

We consider the Demand Strip Packing problem (DSP), in which we are given a set of jobs, each specified by a processing time and a demand. The task is to schedule all jobs such that they are finished before some deadline D while minimizing the peak demand, i.e., the maximum total demand of tasks executed at any point in time. DSP is closely related to the Strip Packing problem (SP), in which we are given a set of axis-aligned rectangles that must be packed into a strip of fixed width while minimizing the maximum height. DSP and SP are known to be NP-hard to approximate to within a factor smaller than 3/2.  

We present a tight (3/2 + ε)-approximation algorithm for DSP that runs in polynomial time for every constant ε > 0, improving upon the previous best approximation ratio of 5/3 +ε. For achieving this best possible approximation guarantee, we prove a global structural result about all optimal solutions: either all jobs with demand greater than OPT/2 are sorted by this parameter and are scheduled one after the other, or the schedule can fit one extra job with demand OPT and width D/50 while maintaining a peak demand of at most (3/2+ε)OPT.

WL meet VC: Generalization abilities of graph neural networks (Morris)

In this talk, we shed some light on the generalization abilities of graph neural networks (GNNs) in various settings. First, we establish a tight connection between the 1-dimensional Weisfeiler-Leman algorithm and the VC dimension of GNNs. Secondly, we use the data margin as a parameter to provide insights into when more expressive variants of GNNs provably generalize.

Homomorphism Counts for Graph Neural Networks: All About That Basis (Jin)

In our recent work, we study the expressivity of graph neural networks (GNNs) with respect to injecting graph motif parameters. Specifically, we show that using the homomorphsim basis of a parameter instead of the parameter itself yields a more fine-grained approach that results in more expressive architectures. We see that this holds at both the graph- and node-level, and it also applies to higher-order GNNs.

Fractional Colorings of Random Hypergraphs (Zakharov)

The work deals with estimating the (4:2)-colorability threshold for a random k-uniform hypergraph in the binomial model H(n, k, p). We consider the sparse case, when the expected number of edges is a linear function of n, i.e. p {n \choose k} = cn, and c > 0, k \geq 3 are some fixed constants. We show that the threshold constant can be expressed as log 6 \cdot 2^{k-2} - {\log 6 \over 2} + g(k), where g(k) is exponentially small.

Connected k-Center and k-Diameter Clustering (Röglin)

Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graph G on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G. Our main result is an O(1)-approximation algorithm for the connected k-center and k-diameter problem for Euclidean spaces of low dimension (constant d) and for metrics with constant doubling dimension. For general metrics, we get an O(log^2(k))-approximation. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model. 

Based on joint work with Lukas Drexler, Jan Eube, Kelin Luo, Melanie Schmidt, and Julian Wargalla.

Tight Inapproximability for Graphical Games (Deligkas)

In this paper, we provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied approximation notions: ε-Nash equilibria (ε-NE) and ε-well-supported Nash equilibria (ε-WSNE), where ε is in [0,1]. We prove that computing an ε-NE is PPAD-complete for any constant ε smaller than 1/2, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a 1/2-NE. On the other hand, we show that computing an ε-WSNE is PPAD-complete for any constant ε smaller than 1, while a 1-WSNE is trivial to achieve, because any strategy profile is a 1-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player.

The Impact of Cooperation in Bilateral Network Creation (Lenzner)

Many real-world networks, like the Internet or social networks, are not the result of central design but instead the outcome of the interaction of local agents that selfishly optimize their individual utility. The well-known Network Creation Game by Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker (PODC'03) models this. There, agents corresponding to network nodes buy incident edges towards other agents for a price of alpha > 0 and simultaneously try to minimize their buying cost and their total hop distance. Since in many real-world networks, e.g., social networks, consent from both sides is required to establish and maintain a connection, Corbo and Parkes (PODC'05) proposed a bilateral version of the Network Creation Game, in which mutual consent and payment are required in order to create edges. It is known that this cooperative version has a significantly higher Price of Anarchy compared to the unilateral version. On the first glance this is counter-intuitive, since cooperation should help to avoid socially bad states. However, in the bilateral version only a very restrictive form of cooperation is considered. We investigate this trade-off between the amount of cooperation and the Price of Anarchy by analyzing the bilateral version with respect to various degrees of cooperation among the agents. With this, we provide insights into what kind of cooperation is needed to ensure that socially good networks are created. As a first step in this direction, we focus on tree networks and present a collection of asymptotically tight bounds on the Price of Anarchy that precisely map the impact of cooperation. Most strikingly, we find that weak forms of cooperation already yield a significantly improved Price of Anarchy. In particular, the cooperation of coalitions of size 3 is enough to achieve constant bounds. Moreover, for general networks we show that enhanced cooperation yields close to optimal networks for a wide range of edge prices. 

Optimal Stopping with Behaviorally Biased Agents (Oren)

People are often reluctant to sell a house, or shares of stock, below the price at which they originally bought it. While this is generally not consistent with rational utility maximization, it does reflect two strong empirical regularities that are central to the behavioral science of human decision-making: a tendency to evaluate outcomes relative to a reference point determined by context (in this case the original purchase price), and the phenomenon of loss aversion in which people are particularly prone to avoid outcomes below the reference point. Here we explore the implications of reference points and loss aversion in optimal stopping problems, where people evaluate a sequence of options in one pass, either accepting the option and stopping the search or giving up on the option forver. The best option seen so far sets a reference point that shifts as the search progresses, and a biased decision-maker's utility incurs an additional penalty when they accept a later option that is below this reference point.

Based on joint work with Jon Kleinberg and Bobby Kleinberg.

Networks and epidemics (Stegehuis)

In real-world networks, nodes often cluster into groups, also called communities. But what is the influence of these local structures on the speed at which an epidemic spreads? Interestingly, we show that community structures can both enforce as well as inhibit epidemic processes, but that many effects that have previously been claimed on the influence of clusters on epidemics may in fact be attributed to the network degrees rather than their clustered structures.  We then investigate to what extent contact tracing can reduce the final size of an epidemic, which strongly depends on the network structure. In contrast to previous findings, contact tracing is not necessarily more effective on networks with heterogeneous degrees. We also show that network clustering influences the effectiveness of the tracing process in a non-trivial way: depending on the infectiousness parameter, contact tracing on clustered networks may either be more, or less efficient than on networks without clustering.

Local averaging in distributed networks and hoping for the best (Mallmann-Trenn)

In this talk we look at the setting where nodes in a network have an initial value and in every time step pick one random neighbour and average. We consider how the average changes over time when the averaging is done unidirectionally (only one node updates its value) and how it changes when some noise is added to every value sent.

On the Hierachy of Distributed Majority Protocols (Rau)

We study the consensus problem among n agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called $j$-Majority: when activated, every agent samples $j$ other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: (j+1)-Majority (for j > 1) converges stochastically faster than j-Majority for any initial opinion configuration. In our analysis we use Strassen's Theorem to prove the existence of a coupling.

In search of useful temporal graph parameters (Meeks)

A highly successful approach for tackling NP-hard problems on graphs is the paradigm of parameterised complexity: the running time of algorithms is analysed in terms of a secondary measure, or parameter, in addition to the total input size, and the goal is to restrict the combinatorial explosion to the parameter (which is hopefully, in instances of interest, much smaller than the total input size). Many widely used parameters capture structural properties of the input graph, for example the edit distance to some class on which the problem is tractable, or the ease with which the graph can be decomposed according to specific rules. In recent years, there have been numerous attempts to apply the parameterised approach to algorithmic problems on temporal graphs, in which the edge-set changes over time. However, this has led to efficient parameterised algorithms in only a few cases: for many natural problems (including some that are polynomial-time solvable on static graphs) the additional complexity introduced by encoding temporal information in the graph renders the temporal versions intractable even when the underlying graph has very simple structure (e.g. when it is a tree or even a path). This motivates the search for new parameters, specifically designed for temporal graphs, which capture properties of the temporal information in addition to the structure of the underlying graph. In this talk I will survey recent progress in the development of such parameters and highlight a large number of remaining challenges.

Supercritical percolation on high-dimensional product graphs (Kang)

We consider a random subgraph obtained by bond percolation on high-dimensional product graphs in the supercritical regime. We derive expansion properties of its giant component from isoperimetric properties of the underlying product graphs. As a consequence we obtain upper bounds on the diameter of the giant component and the mixing time of the lazy simple random walk on the giant component. This talk is based on joint work with Sahar Diskin, Joshua Erde, and Michael Krivelevich.

Prophet Inequalities over Time (Pitschmann)

We introduce an over-time variant of the well-known prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide for each step how long we select the value. Then we cannot select another value until this period is over. The goal is to maximize the expectation of the sum of selected values. We describe the structure of the optimal stopping rule and give upper and lower bounds on the prophet inequality. In online algorithms terminology, this corresponds to bounds on the competitive ratio of an online algorithm.

We give a surprisingly simple algorithm with a single threshold that results in a prophet inequality of approx. 0.396 for all input lengths n. Additionally, as our main result, we present a more advanced algorithm resulting in a prophet inequality of approx. 0.598 when the number of steps tends to infinity. We complement our results by an upper bound that shows that the best possible prophet inequality is at most the inverse of the golden ratio, which is approx. 0.618.

Being an Influencer is Hard (Goldsmith)

We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on four objective functions. In the first objective, the goal is to maximize the total number of vertices that get infected at least once. In the second objective, the goal is to maximize the number of vertices that are infected at the same time step. In the third objective, the goal is to maximize the number of vertices that are infected at a given time step. Finally, in the fourth objective, the goal is to maximize the total number of vertices that get infected every d time steps. We perform a thorough complexity theoretic analysis for these four objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of the first objective for periodic graphs, are intractable even for very simple underlying graphs.

Multi-Agent Contracts (Duetting)

We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy.
Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of ``prices'' and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest.
Our second main result is an $\Omega(\sqrt{n})$ impossibility for settings with n agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.

Preprint: https://arxiv.org/abs/2211.05434 (to appear in STOC 2023)

Information Design for Congestion Games with Unknown Demand (Koglin)

We consider non-atomic congestion games with affine costs and a single commodity whose demand is unknown to the players of the game, but can be observed by a principal. Prior to observing the demand, the principal commits to a public signaling scheme that governs to which extend (if at all) the information about the realized demand is communicated to the players. Upon receiving the signal, the players update their beliefs about the demand and respond by playing a Wardrop equilibrium for the resulting cost functions. We study the question of how to compute the signaling scheme that minimizes the total cost of the induced Wardrop equilibrium.

First, we devise a fully polynomial-time approximation scheme (FPTAS) for the case that the demand can only take two values. The FPTAS relies on several structural properties of the cost of the induced Wardrop equilibrium as a function of the updated belief of the distribution of demands. We show that this function is piecewise linear for any number of demands, and monotonic for two demands. Second, we give a complete characterization of the graph structures where it is optimal for the principal to fully reveal the information about the realized demand to the players. Specifically, we show that this signaling scheme is optimal for all cost functions and probability distributions over demands if and only if the graph is series-parallel. Third, we propose an algorithm that computes the optimal signaling scheme for any number of demands whose time complexity is polynomial in the number of supports that occur in a Wardrop equilibrium for some demand. Finally, we conduct a computational study that tests this algorithm on real-world instances.

Joint work with Svenja M. Griesbach, Martin Hoefer and Max Klimm.

Computational Study of Collective Behavior:  The Case of Association Football (Soccer) (Brandes)

I will present team sports analytics as an opportunity to teach and develop computational methods for the study of collective behavior and applied data science more generally.
Football is the most popular sport in the world, in part because its fluidity and randomness allow for many alternative interpretations of the same events or, in other words, accommodate millions of pundits relying on experience and anecdotal evidence. The discussions around data-informed or even data-driven decision- making illustrate nicely the conflict between naive eagerness to apply, and ignorant dismissal of, soccer analytics.
Using examples from our ongoing research I will discuss opportunities and pitfalls in the (un)critical application of computational methods.
Given that so many seem to know so much about the subject, I expect a great deal of willingness to question any choice of representation or data-suggested conclusion. Why, then, should similar methods be more applicable in unregulated social environments?

Certifying Induced Subgraphs in Large Graphs (Tran)

We introduce I/O-efficient certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class. Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership. On a graph with n vertices and m edges, our algorithms take O(Sort(n + m)) I/Os in the worst case for split, threshold and trivially perfect graphs. In the same complexity bipartite and bipartite chain graphs can be certified with high probability. We provide implementations for split and threshold graphs and provide a preliminary experimental evaluation.

Algorithmic Programmable Matter: From Local Markov Chains to “Dumb” Robots (Richa)

Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials. We describe programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute distributed, local algorithms to self-organize and solve system-wide problems, such as movement, reconfiguration, and coordination. Self-organizing particle systems (SOPS) have many interesting potential applications like coating objects for monitoring and repair purposes, and forming nano-scale devices for surgery and molecular-scale electronic structures. We describe some of our work on the algorithmic foundations of programmable matter, investigating how macro-scale system behaviors can naturally emerge from local micro-behaviors by individual particles: We utilize tools from statistical physics and Markov chain analysis to translate Markov chains defined at a system level into distributed, local algorithms for SOPS that drive the desired emergent collective behavior for the problems of compression, separation, and foraging, among others. We further establish the notion of algorithmic matter, where we leverage standard binary computation, as well as physical characteristics of the robots and interactions with the environment in order to implement our micro-level algorithms in actual testbeds composed of robots that are not capable of any standard computation. We conclude by addressing full concurrency and asynchrony in SOPS.

Dynamic Averaging Load Balancing on Arbitrary Graphs (Hintze)

Triangle Switches, Reconstruction and Mixing (Greenhill)

The Hitting Time of Clique Factors (Müller)

In 2022, Jeff Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let r be an integer larger than two and n divisible by r. Then, in the r-uniform random hypergraph process on n vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. We transfer this hitting time result to the setting of clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph on r vertices K_r, the random graph process contains a K_r-factor. Our proof draws on a novel sequence of couplings, extending techniques of Riordan and Annika Heckel. Moreover, we prove an analogous result for clique factors in the s-uniform hypergraph process (where s is at least 3).

This talk is based on joint work with Annika Heckel, Marc Kaufmann and Matija Pasch.

The Cut Metric for Probability Distributions (Hahn-Klimroth)

Guided by the theory of graph limits, we investigate a variant of the cut metric for limit objects of sequences of discrete probability measures.

Hedonic Games with Fixed-Size Coalitions (Bilò)

In hedonic games, a set of n agents, having preferences over all possible coalition structures, needs to agree on a stable outcome. In this work, we initiate the study of hedonic games with fixed-size coalitions, where the set of possible coalition structures is restricted as follows: there are k coalitions, each coalition has a fixed size, and the sum of the sizes of all coalitions equals n. We focus on the basic model of additively separable hedonic games with symmetric valuations, where an agent's preference is captured by a utility function which sums up a contribution due to any other agent in the same coalition. In this setting, an outcome is stable if no pair of agents can exchange coalitions and improve their utilities. Conditioned on the definition of improvement, three stability notions arise: swap stability under transferable utilities, in which no swap can improve the sum of the utilities of both agents, strict swap stability, in which no swap can improve the utility of one agent without decreasing the utility of the other one, and swap stability, in which no swap can improve the utilities of both agents simultaneously. We analyse the fundamental questions of existence, complexity and efficiency of stable outcomes, and that of complexity of a social optimum.

Margin of Victory for Weighted Tournament Solutions (Döring)

Determining how close a winner of an election is to becoming a loser, or distinguishing between different possible winners of an election, are major problems in Computational Social Choice. We tackle these problems for so-called weighted tournaments by generalizing the notion of Margin of Victory (MoV) for unweighted tournament solutions by Brill et al. to weighted tournament solutions. For these, the MoV of a winner (resp. loser) is the total weight that needs to be changed in the tournament to make them a loser (resp. winner). We study three weighted tournament solutions: Borda's rule, the weighted Uncovered Set, and Split Cycle. For all three rules, we analyse the complexity of computing the MoV, and provide structural insight into the MoV by investigating three properties: monotonicity, consistency regarding the weighted covering relation, and consistency regarding the degree of alternatives. Lastly, we provide upper and lower bounds on the MoV and analyse the expressiveness of the MoV values for each of the three tournament solutions using experimental results on tournaments of varying sizes.

Online Stochastic Optimization (Gravin)

There is a growing number of interesting stochastic models complementing traditional for the area of online algorithms worst-case analysis. Two popular stochastic frameworks are the random arrival model and Bayesian optimization framework. I will introduce these two frameworks on the examples of Secretary problem and Prophet inequality and discuss a few of their combinatorial extensions. A special attention will be given to various online matching models, a central setting for online algorithms due to its many applications in online advertisement, ridesharing, and online marketplaces. I will give an overview of different models and open research directions. No background knowledge is required, although some familiarity with online algorithms and stochastic optimization might be useful.

Based on a series of papers with Tomer Ezra, Michal Feldman, Enze Sun, Zhihao Tang, Hongao Wang, and Kangning Wang

New Fairness Notions for Resource Allocation (Varricchio)

We consider the fundamental problem in resource allocation that entails fairly dividing a set of indivisible goods among agents. The notion of envy-freeness up to any good (EFX) is the most compelling notion of fairness in this line of work. We say an allocation is EFX if every agent (weakly) prefers her own bundle over any other agent bundle after removing her least preferred good from this latter. Despite significant efforts over the past few years, the existence of EFX allocations is not known, even for additive valuations. Therefore, there has been a lot of work focusing on relaxations and approximations of EFX.

In our work, we propose two natural fairness notions that are inspired by EFX. The first notion is the one of epistemic EFX (EEFX), which ensures every agent is EFX-satisfied upon a redistribution of the other agents' goods. The second is the minimum EFX value (MXS) which is a threshold-based criteria defined using EFX allocations. Interestingly, we show that both EEFX and MXS allocations are always guaranteed to exist, for additive valuations, and can be computed in polynomial time.

Joint work with Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, and Eklavya Sharma

Towards Rapidly Transforming Programmable Matter (Scheideler)

The Amoebot model is a model for programmable matter that has found increased interest in recent years. However, many important issues are not captured in the basic form of this model, including rapid shape transformation. I propose a reconfigurable circuit extension that allows many central problems like leader election, compass alignment, and symmetry checks to be solved significantly faster than in the basic model. This provides the base for synchronization and energy distribution that can then be used for rapid shape transformation.

On the Hierarchy of Distributed Majority Protocols (Schallmoser)

We study the Consensus problem among n agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called j-Majority: when activated, every agent samples j other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: (j + 1)-Majority (for j > 1) converges stochastically faster than j-Majority for any initial opinion configuration. In our analysis we use Strassen’s Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [2017]

Online Routing and Network Design with Predictions (Megow)

Online optimization refers to solving problems where an initially unknown input is revealed incrementally, and irrevocable decisions must be made not knowing future requests. The assumption of not having any prior knowledge about future requests seems overly pessimistic. Given the success of machine-learning methods and data-driven applications, one may expect to have access to predictions about future requests. However, simply trusting them might lead to very poor solutions as these predictions come with no quality guarantee. In this talk we present recent developments in the young line of research that integrates such error-prone predictions into algorithm design to break through worst case barriers. We discuss algorithmic challenges with a focus on online   routing and network design and present algorithms with performance guarantees depending on a novel error metric.

Joint work with Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Leen Stougie, and Michelle Sweering.

Algorithms for Non-Linear Preferential Attachment (Allendorf)

Preferential attachment lies at the heart of many network models aiming to replicate features of real world networks. To simulate the attachment process, conduct statistical tests, or obtain input data for benchmarks, efficient algorithms are required that are capable of generating large graphs according to these models.

Existing graph generators are optimized for the most simple model, where new nodes that arrive in the network are connected to earlier nodes with a probability $P(h) \propto d$ that depends linearly on the degree $d$ of the earlier node $h$. Yet, some networks are better explained by a more general attachment probability $P(h) \propto f(d)$ for some function $f \colon \mathbb N~\to~\mathbb R$.
Here, the polynomial case $f(d) = d^\alpha$ where $\alpha \in \mathbb R_{>0}$ is of the greatest interest.

In this paper, we present efficient algorithms that generate graphs according to the more general models.
To this end, we design a new method for maintaining a discrete distribution which leads to a simple yet optimal algorithm for the polynomial model. We parallelize the algorithm by identifying batches of samples that can be drawn independently and obtain a near-optimal speedup when adding many  nodes.
In addition, we present an I/O-efficient algorithm for use in external memory that can even be used for the fully general model.

To showcase the efficiency and scalability of our algorithms, we conduct an experimental study and compare their performance to existing solutions for the linear case.

Strong Approximations and Irrationality in Financial Networks with Derivatives (Ioannidis)

Financial networks model a set of financial institutions (firms) interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps, a certain kind of financial derivatives. The main computational challenge for such systems is known as the clearing problem, which is to determine which firms are in default and to compute their exposure to systemic risk, technically known as their recovery rates. It is known that the recovery rates form the set of fixed points of a simple function, and that these fixed points can be irrational. We further study the clearing problem from the point of view of irrationality and approximation strength. Firstly, we observe that weakly approximate solutions may contain misleading information regarding the actual financial state of an institution, thus making them hard to justify. On this basis, we study the complexity of finding a strongly (or "near") approximate solution, and show FIXP-completeness. We then study the structural properties required for irrationality, and we give necessary conditions for irrational solutions to emerge: The presence of certain types of cycles in a financial network forces the recovery rates to take the form of roots of non-linear second- or higher-degree polynomials. In the absence of a large subclass of such cycles, we study the complexity of finding an exact fixed point, which we show to be a problem close to, albeit outside of PPAD.

The Full Rank Condition for Sparse Random Matrices (Rolvien)

We derive a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the
rows and columns having full row rank. The result covers both matrices over finite fields with independent non-zero entries and {0, 1}-matrices over the rationals. The sufficient condition is generally necessary as well.

Introducing JUNE - an open-source epidemiological simulation (Krauss)

We constructed a detailed digital twin of the UK population, with supreme social and geographical granularity, representing 55 million residents in England and Wales and tracing their daily movements and activities. The infection is propagated through the virtual population through simulated social contacts, and the progress of the disease in infected individuals and their trajectory through the healthcare system is then described, based on public health data.  Various concurrent strains and pharmaceutical (vaccines) and non-pharmaceutial interventions (e.g. social distancing) are implemented.  JUNE resolves the spatio-temporal development of the disease spread through the population in great detail and is able to find non-trivial correlations of infection and fatality rares with a variety of societal factors.  Our model has been proven in the midst of the current crisis and is currently being used by NHS-England’s COVID-19 response team to inform their strategic and operational planning.  As a side-product, we collaborate with WHO and UN Global Pulse and roll out the model also to one of the world's largest refugee settlements.

Initial alignment in neural networks and its necessity for learning by gradient descent (Hązła)

We study the question which boolean functions can be efficiently learned by neural networks using gradient descent (GD) algorithm. We introduce the notion of "initial alignment" (INAL) between a randomly initialized neural network and its target function. We then show that if the INAL value is not noticeably large, then a fully connected neural network with iid initialization will not learn the function with noisy GD in polynomial time. The result is based on analyzing the relation of INAL to the boolean Fourier expansion and the notion of cross-predictability of a class of functions.

Joint work with Emmanuel Abbe, Elisabetta Cornacchia and Christopher Marquis.

Single-source Shortest p-disjoint Paths: Fast Computation and Sparse Preservers (Bilò)

On the External Validity of Average-Case Analyses of Graph Algorithms (Fischbeck)

The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input.
With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.

Competitive Divison of Goods, Bads, and Mixed (Mehta)

Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This age-old problem, mentioned even in the Bible, arises naturally in a wide range of real-life settings, for example, school seat assignments, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are non-disposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed).

I will first consider the case of additive valuations, where when all items are goods, the CE set is well-known to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with chores, the CE set may be nonconvex and disconnected. I will discuss how to handle this non-convexity through a new exterior-point method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinate-wise monotone function over linear constraints. Finally, I will discuss recent developments on the exchange setting (barter system).

Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Jugal Garg, and Peter McGlaughlin.

Public Signals in Network Congestion Games (Koglin)

We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate within any non-trivial bounds, even for affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium. For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature.

This is joint work with Svenja Marie Griesbach, Martin Hoefer and Max Klimm.

Similarity-based hierarchical Clustering in Tree-Like Networks (Mnich)

Hierarchical clustering of networks is a fundamental task with important applications in phylogenetics, network security analysis, and software engineering, which groups together data points that are similar to each other, and separates data points which are different. Compared to flat clustering, which requires to guess or search the "optimal" number of groups or clusters in advance, hierarchical clustering does not have such a requirement. Moreover, hierarchical clustering can detect the hidden cluster structure at all levels of granularity simultaneously.

This concept of hierarchical clustering was formulized by Dasgupta (STOC 2016), who proposed algorithms based on sparsest cut computations to identify the similarity and dissimilarities in large networks. For tree-like networks of treewidth t and size n, Chlamtáč et al. (APPROX 2010) presented an algorithm that yields an exp(exp(t))-approximation to the optimal sparsest cut in  in time exp(t) * poly(n). Gupta et al. (STOC 2013) showed how to obtain an O(1)-approximation with a blown-up run time of n^{O(k)}. An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, an O(1)-approximation in time exp(k) * poly(n). We achieve this goal, via the following results: (i) An O(k^2)-approximation that runs in time exp(k) * poly(n), simultaneously improving both the approximation factor and the run time of the result by Chlamtáč et al. (ii) For any \varepsilon>0, an O(1/\varepsilon^2)-approximation in time 2^{O(k^{1+\varepsilon}/\varepsilon)} * poly(n), implying an O(1)-approximation whose run time is almost exp(k) * poly(n) and a O(\log^2 k)-approximation in time k^{O(k)} * poly(n). Key to our results is a novel measure of "combinatorial diameter" for tree-like networks, that we introduce here and which may be of independent interest.

(Joint work with Parinya Chalermsook, Matthias Kaul, Joachim Spoerhase and Daniel Váz).

Engineering Uniform Sampling of Graphs with a Prescribed Power-law Degree-Sequence (Allendorf)

We consider the following common network analysis problem: given a degree sequence d = (d_1, ..., d_n) in N^n return a uniform sample from the ensemble of all simple graphs with matching degrees. In practice, the problem is typically solved using Markov Chain Monte Carlo approaches, such as Edge-Switching or Curveball, even if no practical useful rigorous bounds are known on their mixing times.In contrast, Arman et a. sketch Inc-Powerlaw, a novel and much more involved algorithm capable of generating graphs for power-law bounded degree sequences with gamma > 2.88 in expected linear time. For the first time, we give a complete description of the algorithm and add novel switchings. To the best of our knowledge, our open-source implementation of Inc-Powerlaw is the first practical generator with rigorous uniformity guarantees for the aforementioned degree sequences. In an empirical investigation, we find that for small average-degrees Inc-Powerlaw is very efficient and generates graphs with one million nodes in less than a second. For larger average-degrees, parallelism can partially mitigate the increased running-time.

Dynamics for Multi-Agent System Coordination in Noisy and Stochastic Environments (Natale & D'Amore)

In recent years, there has been a surge of interest in the study of abstract systems composed of simple interacting agents. In particular, some computer scientists have focused their attention on algorithms that attempt to capture aspects of biological systems, i.e., natural algorithms. Here, we consider two distributed computing tasks that affect many biological systems: the consensus problem and the ANTS problem. When trying to reach consensus, real entities may be affected by some form of communication noise rather than adversarial failures. In this framework, we study two well-known opinion dynamics (the Undecided-State dynamic and the 3-Majority dynamic), which are known to converge quickly to agreement in noise-free environments, to which we add a uniform communication noise feature: we show that both dynamics exhibit similar phase transitions. In the ANTS (Ants Nearby Treasure Search) problem, on the other hand, a system of independent agents in the two-dimensional lattice must find a given (unknown) target as fast as possible. We consider Lévy walks, special random walks that have been shown to model many animal movement patterns, and show that they can provide a near-optimal solution to the ANTS problem. These results are based on the works [d'Amore et al., SIROCCO 2020], [Clementi et al., PODC 2021], and [d'Amore et Ziccardi, SIROCCO 2022], wich are joint work with A. Clementi, G. Giakkoupis, E. Natale, and I. Ziccardi.

Population Protocols for Exact Plurality Consensus: How a small chance of failure helps to eliminate insignificant opinions
(Schallmoser)

Joint work with Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, and Peter Kling

New Perspectives on Classic Questions in the Theory of Graph Algorithms (Nanongkai)

The theory of graph algorithms is a research field that develops mathematical techniques with provable guarantees to eventually make computing devices process graph (network) data with fewer resources such as time, energy, and hardware. Despite its pivotal role in computer science over many decades, the theory of graph algorithms research still lacks techniques for designing efficient algorithms for some of the most basic tasks, and for exploiting technological advances from the last few decades: On the one hand, the ever-increasing data volumes call for nearly-linear time algorithms which are still elusive for many basic problems. On the other hand, to exploit advances in computer architecture and large-scale systems, we need algorithms that are efficient in models of computation beyond the classic sequential setting.
In this talk, I will discuss some recent progress towards efficient algorithms across many computational models such as dynamic graphs, distributed networks, and streaming algorithms. Basic graph problems that will be discussed include cut, matching, and shortest paths. No background is required, although familiarity with basic graph terminologies and algorithms will be useful.

Semi-Definite Programming meets Stance Classification - how to turn theory into good practice (Vilenchik)

Stance detection is an important task, supporting many downstream tasks such as discourse parsing and modeling the propagation of fake news, rumors, and science denial. In this talk we describe a novel framework for stance detection. Our framework is unsupervised and domain-independent. Given a claim and a multi-participant discussion - we construct the interaction network from which we derive topological embeddings for each speaker. These speaker embeddings enjoy the following property: speakers with the same stance tend to be represented by similar vectors, while antipodal vectors represent speakers with opposing stances. These embeddings are then used to divide the speakers into stance-partitions. Our embedding is derived from the Semi-Definite Programming (SDP) solution to the max-cut problem on the interaction network. In this talk we shall explain how the success of our method is rooted in theoretical results of SDP integrality for random k-colorable graphs. We evaluated our method on three different datasets from different platforms. Our method outperforms or is comparable with supervised models, including Neural Network based approaches. Joint work with: Ron Korenblum Pick, Vladyslav Kozhukhov, and Oren Tsur Paper was accepted to AAAI 2022: https://arxiv.org/abs/2112.00712 .

A sparse parity matrix (Lee)

We study a square matrix with every entry having a Bernoulli distribution p=d/n. We show that this matrix defies the usual zero-one law behavior when d>e such that the fraction of the variables that take the same value in the kernel of the matrix vacillates between two values with equal probability 1/2.

On The Unreasonable Effectiveness of SAT Solvers (Ganesh)

Over the last two decades, software engineering (broadly construed to include testing, analysis, synthesis, verification, and security) has witnessed a silent revolution in the form of Boolean SAT and SMT solvers. These solvers are now integral to many testing, analysis, synthesis, and verification approaches. This is largely due to a dramatic improvement in the scalability of these solvers vis-a-vis large real-world formulas. What is surprising is that the Boolean satisfiability problem is NP-complete, believed to be intractable, and yet these solvers easily solve industrial instances containing millions of variables and clauses in them. How can that be? In my talk, I will address this question of why SAT solvers are so efficient through the lens of machine learning (ML) as well as ideas from (parameterized) proof complexity. While the focus of my talk is almost entirely empirical, I will show how can we leverage theoretical ideas to not only deepen our understanding but also to build better SAT solvers. I will argue that SAT solvers are best viewed as proof systems, composed of two kinds of sub-routines, ones that implement proof rules and others that are prediction engines that optimize some metric correlated with solver running time. These prediction engines can be built using ML techniques, whose aim is to structure solver proofs in an optimal way. Thus, two major paradigms of AI, namely machine learning and logical deduction, are brought together in a principled way in order to design efficient SAT solvers. A result of my research is the MapleSAT solver, that has been the winner of several recent international SAT competitions and is widely used in industry and academia.

The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability (Rothenberger)

Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.

Incomplete Information VCG Contracts for Common Agency (Talgam-Cohen)

We study contract design for welfare maximization in the well-known “common agency” model of Bernheim and Whinston [1986]. This model combines the challenges of coordinating multiple principals with the fundamental challenge of contract design: that principals have incomplete information of the agent’s choice of action. Motivated by the significant social inefficiency of standard contracts for such settings (which we formally quantify using a price of anarchy/stability analysis), we investigate whether and how a recent toolbox developed for the first set of challenges under a complete-information assumption - VCG contracts [Lavi and Shamash, 2019] - can be extended to incomplete information. This is joint work with Tal Alon, Ron Lavi and Elisheva Shamash.

Delegated Online Search (Hahn)

In a delegation problem, a principal with commitment power tries to pick one out of n options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, the principal delegates the information acquisition to a rational and self-interested agent. After inspection, the agent proposes one of the options, and the principal can accept or reject.

We study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for the principal that approximate the utility of her best option in hindsight?

Temporal Graph Exploration (Erlebach)

A temporal graph is a sequence of static graphs that all have the same vertex set, but the edge set in each step can be different. An agent can in each step either stay at its current vertex or move over an incident edge that is present in that step. The goal is to let the agent visit all vertices of the temporal graph as quickly as possible. While it is easy to visit all vertices of a static graph with n vertices in O(n) steps (e.g., by using depth-first search), the exploration of temporal graphs may require a much larger number of steps: We show that even if the temporal graph is a connected graph in each step and the dynamics are fully known in advance, exploration may require a quadratic number of steps. We also present upper and lower bounds on the worst-case exploration time of temporal graphs for various restricted cases (e.g., restrictions on the underlying graph or on the maximum degree of the graph in each step), outlining the main techniques that have been used to obtain these bounds and highlighting the many cases with large gaps between the known upper and lower bounds. (The talk is based on joint work with Michael Hoffmann, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob Spooner.)

A loosely self-stabilizing leaderless phase clock (Hahn)

We present a self-stabilizing phase clock for population protocols. In the population model we are given a system of n identical agents which interact in a sequence of randomly chosen pairs. Our phase clock is leaderless and it requires O(log n) states. It runs forever and is, at any point of time, in a synchronous state w.h.p. When started in an arbitrary configuration, it recovers rapidly and enters a synchronous configuration within O(log n) parallel time w.h.p. Once the clock is synchronized, it stays in a synchronous configuration for at least poly n parallel time w.h.p.

Learning to prune instances of combinatorial optimisation problems (Ajwani)

In a large number of industrial applications, combinatorial optimisation problems are repeatedly solved with datasets from similar distribution. In recent years, machine learning techniques have been shown to be quite effective in speeding up such computations. However, black-box end-to-end machine learning approaches suffer from poor interpretability and the requirement for a large amount of labelled data. In this talk, I will present a simple and highly effective machine learning framework that incorporates the insights from the algorithmic and optimization literature to speed-up the solutions of these problems. We look at the kind of quantities the approximation algorithms employ and use these to derive useful features for training a classifier that helps quickly reduce the problem size by identifying the difficult core of the problem and pruning the remainder. The difficult core is then solved using an ILP solver. A prime advantage of using such features is that we do not require much data to train the classifier.
I will present results on a range of combinatorial optimisation problems: maximum clique enumeration, k-median, facility location, set cover, maximum coverage, minimum steiner tree, travelling salesman problem, capacitated vehicle routing problem and nurse rostering problem. I will show that in all of these problems, the learning-to-prune framework is able to reduce the computation time drastically while still obtaining a close to optimal solution.

An Experimental Study of External Memory Algorithms for Connected Components (Tran)

We empirically investigate algorithms for solving Connected Components in the external memory model. In particular, we study whether the randomized O(Sort(E)) algorithm by Karger, Klein, and Tarjan can be implemented to compete with practically promising and simpler algorithms having only slightly worse theoretical cost, namely Borůvka’s algorithm and the algorithm by Sibeyn and collaborators. For all algorithms, we develop and test a number of tuning options. Our experiments are executed on a large set of different graph classes including random graphs, grids, geometric graphs, and hyperbolic graphs. Among our findings are: The Sibeyn algorithm is a very strong contender due to its simplicity and due to an added degree of freedom in its internal workings when used in the Connected Components setting. With the right tunings, the Karger-Klein-Tarjan algorithm can be implemented to be competitive in many cases. Higher graph density seems to benefit Karger-Klein-Tarjan relative to Sibeyn. Borůvka’s algorithm is not competitive with the two others.

Spreading Processes on Spatial Contact Networks (Lapinskas)

We study the spread of information (or an epidemic) through a random graph intended to model a real-world social network. A decade ago, it was a long-standing open problem to find any such random graph model which maintained enough independence between vertices and edges to be pleasant to work with. Now, a closely-related family of such models has been developed. We study two models in this family, geometric inhomogeneous random graphs (GIRGs) and scale-free percolation (SFP). GIRGs include as a sub-family arguably the most famous such model: hyperbolic random graphs. The talk will not assume any prior background in the area, and it will begin with an introduction to GIRGs and SFP and to the properties of social networks in general.

From prior work by Komjathy and Lodewijks, we know that if we consider a standard SI spreading model on any GIRG or SFP graph whose parameters give rise to a giant component, then for most reasonable choices of transmission parameters the process will “explode” with non-zero probability (covering a constant proportion of vertices in constant time). This is unrealistic in many situations, which suggests it may be the wrong model for those situations. We show that by adding a small transmission penalty to high-degree vertices, we can recover the expected behaviour of a phase transition to explosion, and we locate this phase transition. We will also discuss unpublished future work in which we determine many of the transitions between explosion, exponential spread, and even polynomial spread. The idea of polynomial spread is surprising, but true to life; some epidemics do spread at polynomial rates, such as ebola in west Africa, and understanding the cause of this phenomenon is an open problem.

On codes decoding error on the BEC and BSC (Hazla)

I will talk about how to use a recent inequality on Boolean functions by Samorodnitsky to obtain a result in coding theory. Namely, assume that a linear code successfully corrects errors on the binary erasure channel (BEC) under optimal (maximum a posteriori, or MAP) decoding. Then, this code is also successful on a range of other channels with somewhat smaller capacities, including binary symmetric channel (BSC). One previously unknown consequence is that constant-rate Reed-Muller codes correct errors on BSC(p) for some constant p > 0.

Warning Propagation on Random Graphs (Ravelomanana)

Warning Propagation is a combinatorial message passing algorithm that unifies and generalises a wide variety of recursive combinatorial procedures. Special cases include the Unit Clause Propagation and Pure Literal algorithms for satisfiability as well as the peeling process for identifying the k-core of a random graph. Here we analyse Warning Propagation in full generality on the binomial random graph. We prove that under a mild stability assumption Warning Propagation converges rapidly. In effect, the analysis of the fixed point of the message passing process on a random graph reduces to analysing the process on a Galton-Watson tree. This result corroborates and generalises a heuristic first put forward by Pittel, Spencer and Wormald in their seminal k-core paper (JCTB 1996).

Networked Contingent Convertible Obligations and Financial Stability (Feinstein)

In this talk we investigate whether a financial system can be made more stable if financial institutions share risk by exchanging contingent convertible (CoCo) debt obligations. The question is framed in a financial network with debt and equity interlinkages with the addition of CoCos that convert continuously when a bank's debt-equity ratio drops to a trigger level. We characterize the clearing problem for the interbank debt and equity at the maturity of the obligations. We then introduce stylized networks to study when introducing CoCo bonds improves financial stability, as well as specific networks for which CoCo bonds do not uniformly provide improved system performance. To return to the main question, we examine the EU financial network at the time of the 2011 EBA stress test to do comparative statics to study the implications of CoCo debt on financial stability.  It is found that by replacing all unsecured interbank debt by standardized CoCo interbank debt securities, systemic risk in the EU will decrease and bank shareholder value will increase. This is joint work with T.R. Hurd (McMaster University).

Stochastical Models for Bipartite Random Graph Models (Gerstorfer)

We study the embedding of bipartite random graph models using Bayesian stochastical models. Given a list of bipartite edges, we use Variational Inference algorithms to estimate the optimal parameters for a generative network model, so that the input network will be a typical outcome of the generative model. In this talk, I will present the methods we use for our models and explain the main concepts of our approach.

Theoretical Algorithm Analysis meets Practical Data (Bläsius)

A theoretical running time analysis is a great tool for predicting the performance of algorithms, saving programmers from implementing and evaluating alternatives that are "obviously" worse. Though this works very well in many cases, there are situations where the predictions do not match practical observations. This often comes from the fact that practical problem instances have certain properties that make them well-behaved. In this talk, I formalize these properties using probabilistic models and discuss theoretical results based on these formalizations. In the course of this, I will discuss advantages and
limitations of this model-based approach.

Eventually Exponential Contagion via Local and Global Contacts (Fischbeck)

Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least r neighbors were active in the previous round. We propose the perturbed percolation process, a superposition of two percolation processes on the same node set. One process acts on a base graph with activation threshold 1, while the other acts on a random graph with threshold r (representing local and global contacts, respectively). We consider a class of grid-like base graphs, in which the bootstrap percolation process only spreads polynomially fast. As random graph, we consider Erdős–Rényi graphs. For r=1, the perturbed percolation process percolates exponentially fast, as the diameter is known to be low. For r>=2 however, we prove that the process initially spreads polynomially fast, with no activations via the random graph, and eventually the activation rate becomes exponential, driven only by the random graph. We complement our theoretical results by empirical analyses of this process. In addition, we discuss future work on the inclusion of recovery into this process.

The Next Economic Crisis? It's the Network! (Wattenhofer)

The world's financial system is a network, where financial institutions such as banks are connected via various kinds of financial contracts. If some financial institutions go bankrupt, then others might suffer as well; the financial network might experience a ripple effect. In other words, the next big financial crisis should be understood with the network in mind. In this talk I will present some analytical results on financial networks. For instance, can we build a financial network that is more robust to failures? How can we clean up after a crisis? Who should be bailed out?

Fire Sale Games (Wilhelmi)

We study a financial network consisting of n players, each write liabilities and hold unmarketable assets as well as a set of marketable assets called securities. Every player is obligated to fulfill a given leverage constraint and is forced to sell a share of its securities for discount prices whenever it violates the constraint. We study fire sales from a game-theoretical view where players sell securities strategically to minimize losses due to decreasing prices. We consider different combinations of price functions and their impact on sales revenue. For a wide range of games, we show monotonic sales of players. Furthermore, we prove existence of equilibria and convergence to the best equilibrium of the best-response dynamic.

Self-Stabilizing Clock Synchronization with 1-Bit Messages (Giakkoupis)

I will talk about some recent results we showed for the problem of distributed clock synchronization. The model we consider is a synchronous fully-connected network of n agents, where each agent has a local clock, that is, a counter increasing by one modulo T in each round. The clocks have arbitrary values initially, and they must all indicate the same time eventually. We assume a gossip-based pull communication model, where in every round each agent receives an ℓ-bit message from a random agent. We devised several fast synchronization algorithms that use small messages and are self-stabilizing, that is, the complete initial state of each agent (not just its clock value) can be arbitrary. Our main contribution is an algorithm that synchronizes a general modulo T clock in polylogarithmic time (in n and T), using just 1-bit messages. This is a join work with Paul Bastide and Hayk Saribekyan.

Using an Oracle for Scheduling Unknown Independent Tasks (Rau)

We are studying a non-clairvoyant problem for scheduling independent tasks where the processing times of the tasks are unknown. However, the scheduler can use an external resource (oracle) that delivers an answer to a query on the processing time. This query for the processing time of a task takes some time and the schedule has to wait until it is answered. Aiming to minimize the total completion time of the given tasks, we study different strategies for which tasks the oracle should be questioned. If this strategy has to be fixed before the first task is queried or scheduled, we present the strategy that provably generates a schedule with the smallest expected total completion time. However, we prove that this strategy is not the best when aiming to minimize the worst case.

Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis (Meyerhenke)

The ubiquity of massive graph data sets in numerous applications requires fast algorithms for extracting knowledge from these data. We are motivated here by three electrical measures for the analysis of large small-world graphs G = (V, E) - i. e., graphs with diameter in O(log |V|), which are abundant in complex network analysis. From a computational point of view, the three measures have in common that their crucial component is the diagonal of the graph Laplacian’s pseudoinverse, L^+. Computing diag(L^+) exactly by pseudoinversion, however, is as expensive as dense matrix multiplication - and the standard tools in practice even require cubic time. Moreover, the pseudoinverse requires quadratic space - hardly feasible for large graphs. Resorting to approximation by, e. g., using the Johnson-Lindenstrauss transform, requires the solution of O(log |V| /ε²) Laplacian linear systems to guarantee a relative error, which is still very expensive for large inputs. In this paper, we present a novel approximation algorithm that requires the solution of only one Laplacian linear system. The remaining parts are purely combinatorial - mainly sampling uniform spanning trees, which we relate to diag(L^+) via effective resistances. For small-world networks, our algorithm obtains a ± ε-approximation with high probability, in a time that is nearly-linear in |E| and quadratic in 1 / ε. Another positive aspect of our algorithm is its parallel nature due to independent sampling. We thus provide two parallel implementations of our algorithm: one using OpenMP, one MPI + OpenMP. In our experiments against the state of the art, our algorithm (i) yields more accurate approximation results for diag(L^+), (ii) is much faster and more memory-efficient, and (iii) obtains good parallel speedups, in particular in the distributed setting. Finally, we sketch some extensions of our techniques to related problems, in particular to (group) forest closeness centrality.

Simulating Population Protocols in Sub-Constant Time per Interaction (Penschuck)

We consider the efficient simulation of population protocols. In the population model, we are given a system of n agents modeled as identical finite-state machines. In each step, two agents are selected uniformly at random to interact by updating their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the
performance of these simulators is the data structure storing the agents' states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the
implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out 2^50 interactions among the same number of agents in less than 400s.

Beyond Sparsity: Compressive Sensing with (Deep) Generative Modeling Assumptions (Scarlett)

The problem of estimating an unknown vector from linear measurements has a long history in statistics, machine learning, and signal processing. Classical studies focus on the "n >> p" regime (#measurements >> #parameters), and more recent studies handle the "n << p" regime by exploiting low-dimensional structure such as sparsity or low-rankness.  Such variants are commonly known as compressive sensing.

In this talk, I will overview recent methods that move beyond these simple notions of structure, and instead assume that the underlying vector is well-modeled by a generative model (e.g., produced by deep learning methods such as GANs).  I will highlight algorithmic works that demonstrated up to 5-10x savings in the number of measurements over sparsity-based methods, and then move on to our theoretical work characterizing the order-optimal sample complexity in terms of quantities such as (i) the Lipschitz constant of the model, or (ii) the depth/width in a neural network model.  I will also briefly overview some recent results on non-linear observation models.

Inference under restrictions - sparsity constrained group testing (Hahn-Klimroth)

While non-adaptive group testing itself was recently fully understood to be easy in the sense that there is a polynomial time algorithm achieving inference at a universal information-theoretic lower bound, it comes with the flaw that within optimal designs each individual gets tested log(n) times and each test contains polynomially many individuals. Such testing schemes may not be applicable due to restrictions in laboratories.

In this talk, we will tackle the problem by analysing the sparsity-constrained group testing problem. Building up on first results by Gandikota et al. (2016), we provide a full understanding of the group testing problem if the test-size needs to be constant and achieve almost optimal results if the tests-per-individual are restricted to o(log n).