Connected Components in a binary image are defined according the graph of its active pixels, each having edges to all of its neighbours. We define neighbourhoods by an arbitrary maximum Chebyshev distance, while previous approaches are limited to four or eight neighbours. Efficient connected component algorithms are introduced with time complexity independent of neighbourhood size. The approach fits well with parallelism; on multi-core hardware, multi-terapixels are analyzed in a few seconds, establishing unprecedented potential for large-scale image processing.

Uniquely among CC algorithms, our method identifies and clusters patterns of localised densities — not unlike DBSCAN, but in a single pass with linear time.

Host: Kim Skak Larsen.

String processing is a central task in modern data analysis. For example, in bioinformatics, DNA sequences are strings over alphabet A,C,G,T. Periodic fragments, such as the repeated "CAG" in the fragment "TCCAGCAGCAGCAA" of the human HTT gene, are structures of fundamental importance. In this example, the number of repetitions of "CAG" varies for each person and is strongly correlated with the likelihood of developing Huntington's disease. From a computer science perspective, periodic fragments also play a fundamental role in the design of efficient algorithms and data structures. They rarely behave like their non-periodic counterparts — their structure usually either enables elegant shortcuts or introduces fundamental complications. In this presentation, we explore the detection of periodic fragments, as well as algorithmic applications in which they are central. In light of the explosive growth of, e.g., DNA sequencing data, we focus on space-efficient algorithms for classic problems such as compression, pattern matching, and indexing. The talk is designed to be accessible to anyone with a general computer science background.

Host: Lars Rohwedder.

In the year 1976, Stockmeyer introduced the so-called polynomial hierarchy, containing the complexity class \( \Sigma^p_2 \). While this class is much lesser-known than the famous class NP, it turns out that \( \Sigma^p_2 \) is the natural complexity class for many problems. This concerns especially problems occurring in the areas of robust optimization algorithms, making decisions under uncertainty, defending infrastructure against attackers, economic games with two players, or more general any optimization problem which can be understood as a two-stage optimization process. Understanding which problems are complete for the class \( \Sigma^p_2 \) is important - under common complexity assumptions, any \( \Sigma^p_2 \)-complete problem cannot be described by a mixed integer program of polynomial size. This means that current existing integer program solvers, which have in some cases been very successful in tackling NP-complete problems, are not very successful at solving the harder case of \( \Sigma^p_2 \)-problems.

In this talk, I will highlight my broad research in the area of \( \Sigma^p_2 \)-complexity (as well as higher levels of the polynomial hierarchy). In particular, I will highlight a series of meta-theorems discovered by my co-authors and me, that state something quite fundamental about min-max optimization. These meta-theorems state that for hundreds of classical famous NP-complete problems, the \( \Sigma^p_2 \) complexity follows "for free" from the NP-completeness of the base version. Thus, it is not necessary to repeat a tedious \( \Sigma^p_2 \)-completeness proof for each problem one is interested. Instead, this fact follows simply from structural properties.

In the second part of the talk, I will briefly lay out how the insights from the first part helped solve a 30 years old conjecture by Frieze and Teng. The diameter of a polytope is a quantity closely tied to the worst-case performance of the famous simplex algorithm. In 1994, Frieze and Teng conjectured that it is \( \text{co-}\Sigma^p_2 \)-complete to compute this quantity. We answer this conjecture in the affirmative. This improves upon partial results by Sanità [FOCS'18] as well as Steiner and Nöbel [SODA'25].

Host: Lars Rohwedder.

An orientation of a graph or mixed graph is obtained by assigning a direction to each of its undirected edges. We focus on the search for orientations satisfying prescribed connectivity properties. This paradigm has been studied throughout the 20th century and is still highly active today.

We first review some classic theorems of Robbins and Nash-Williams. Afterwards, we give an overview of the research building on these theorems, focusing on projects the speaker was involved in. This will include structural and algorithmic problems, also involving parameterized complexity and approximation algorithms.

Finally, we present in some more detail a research project recently completed by the speaker. Here, the objective is to find an orientation that maximizes the number of ordered vertex pairs such that the second vertex is reachable from the first one. Hakimi, Schmeichel, and Young proved that this problem can be solved in polynomial time in undirected graphs and inquired about its complexity in mixed graphs. We prove that the problem becomes NP-hard in mixed graphs, but, on the other hand, can be solved in polynomial time if we fix the number of preoriented arcs.

Host: Lars Rohwedder.

In this talk, I will first provide a broad overview of my research interests, focusing on two main aspects. The first concerns the theory of parameterized algorithms, primarily in the context of graph problems. The second highlights how I apply theoretical insights to problems arising in different application domains, often leading to the resolution of open problems and conjectures.

In the second part of the talk, I will present a recent result illustrating this latter direction. I will introduce the concept of perfect network resilience and show how to decide in linear time whether a given network satisfies this property. Moreover, I will present an algorithm that constructs perfectly resilient forwarding tables in \( O(nm) \) time whenever they exist.

This part of the talk is based on the paper "Perfect Network Resilience in Polynomial Time", which was recently accepted for publication at the 58th ACM Symposium on Theory of Computing (STOC '26) and is joint work with Stefan Schmid.

Host: Lars Rohwedder.

We consider the problem of online preemptive scheduling on a single machine to minimize the total flow time, i.e., the total time that jobs spend in the system. In clairvoyant scheduling, where job processing times are revealed upon arrival, the Shortest Remaining Processing Time (SRPT) algorithm is optimal. However, in practice, exact processing times are often unknown. At the opposite extreme, in non-clairvoyant scheduling, processing times are revealed only upon job completion, which leads to strong lower bounds on the competitive ratio. In this talk, we study intermediate information models between these two extremes. First, we consider \( \varepsilon \)-clairvoyant scheduling, where the processing time of a job is revealed once only an \( \varepsilon \)-fraction of the job remains to be processed, and give a best-possible \( \lceil\frac{1}{\varepsilon}\rceil \)-competitive algorithm. We conclude the talk by discussing the model of scheduling with progress bars, which captures clairvoyant, non-clairvoyant, and \( \varepsilon \)-clairvoyant scheduling and allows us to model a natural setting in which the scheduler receives continuous feedback in the form of progress bars: estimates of the already completed fraction of each job over time. We design new algorithms for adversarial and stochastic progress bars and show strong bounds on the competitive ratio for minimizing the total completion time on a single machine.

Host: Lars Rohwedder.

In this talk, I am going to give an overview of recent developments in perpetual scheduling, with a focus on combinatorial versions. Here, given a set system \( \mathcal{I} \) on a ground set \( E \), a schedule consists of an independent set from \( \mathcal{I} \) for every discrete time step \( t\in\mathbb{N} \), with the objective of fulfilling frequency requirements on the occurrence of elements in \( E \). We focus specifically on combinatorial bamboo garden trimming, where elements accumulate height at growth rates \( g(e) \) for element \( e\in E \) and are reset to zero when scheduled, with the goal of minimizing the maximum height attained by any element. As a normalization, we assume that the vector of growth rates is given as a convex combination of incidence vectors from \( \mathcal{I} \). We prove that, when the set system is a matroid, it is possible to guarantee a maximum height of at most \( 2 \), which is optimal. For general set systems, one can only guarantee a height that is logarithmic in \( |E| \).

The talk is partially based on joint work with Mirabel Mendoza-Cadena, Arturo Merino, and Mads Anker Nielsen.

Host: Kim Skak Larsen.

The Critical Node Cut (CNC) problem is a natural connectivity-based generalization of Vertex Cover. We revisit its parameterized complexity; our main contribution is an improved hardness result, obtained via a recently introduced technique that was first applied to the related Vertex Integrity problem. We also discuss algorithms for further parameterizations. Overall, our results substantially sharpen the known complexity landscape for CNC.

Based on joint work with Dušan Knop and Nikolaos Melissinos, available at https://arxiv.org/abs/2506.23363.

Host: Lars Rohwedder.

We study the generalization of Correlation Clustering which incorporates fairness constraints via the notion of fairlets. The corresponding Fair Correlation Clustering problem has been studied from several perspectives to date but has so far lacked a detailed analysis from the parameterized complexity paradigm. We close this gap by providing tractability results for the problem under a variety of structural graph parameterizations, including treewidth, treedepth and the vertex cover number; our results lie at the very edge of tractability given the known NP-hardness of the problem on severely restricted inputs.

Host: Lars Rohwedder.

In the classical understanding, an online algorithm gets the instance piece by piece and needs to make some action for every piece of the instance without knowing what comes next. While this is practical for many problems, for some it is not. Therefore in recent years, many variants of online problems are studied which relax the setting. In this talk, we will discuss two variants:

A common way to present graphs in an online fashion is by presenting it vertex-wise, with all the edges that are induced by the already presented vertices. However, if an algorithm must decide if each presented vertex is part of a solution set or not, it is easy to find examples for basically every problem that show that the competitive ratio of the online algorithm is arbitrary bad. A way to relax this condition is to not enforce the decision whenever the vertex is presented, but instead only when some property is no longer given. For example, for an online Feedback Vertex Set, it is sensible that the graph is presented vertex-wise, and the online algorithm only needs to add a vertex to the solution set as soon as there is an uncovered circle. If the circle is covered, the instance continues. This concept can be found with the name "Late Accept" or "Delayed Decision". We will mainly discuss the Online Feedback Vertex Set as an example, which has a competitive ratio of something between four and five [1].

Another classical online problem on graphs is the Graph Exploration Problem: Here every vertex of a given graph must be visited as in the classical TSP setting, but here the graph is not known in the beginning. At every point, an algorithm only knows about the already visited vertices and their neighbors. This however is not necessarily a realistic setting: Usually the structure of the graph (for example underlying road network) is known in advance, but the details are not. One usually has a prediction of how long it takes to traverse through a particular road, but due to road conditions or imprecise maps, one might realize that a road will take slightly longer than expected when arriving at it. To deal with those deviations, it is natural to assume that an agent can adapt to the situation: When realizing that taking a particular road is more expensive than expected, recalculating the tour and taking another road instead is possible.

In a sense, this setting lies in between the offline TSP, and the online problem of graph exploration: it allows some computation at the beginning, but remains an online problem during traversal through the graph. For general graphs, we show that no strategy achieves a competitive ratio better than the accuracy factor of the prediction, which can be matched by a simple algorithm. In addition, we will also have a look at restricted graph classes [2].

[1] Delaying Decisions and Reservation Costs; E. Burjons, F. Frei, M. Gehnen, H. Lotze, D. Mock, P. Rossmanith; COCOON 2023
[2] Online Simple Knapsack with Bounded Predictions; M. Gehnen, E. Naquin, R. Klasing; Preprint avilable, 2025

Host: Lars Rohwedder.

Ph.D. defense.

Advisors: Kim Skak Larsen, Lene Favrholdt, Melih Kandemir.

Leader election is a fundamental problem in distributed computing, in which a set of n processes compete to become the leader. At most one process can become the leader. If no processes crash, then exactly one process becomes the leader. The other processes are not required to know which process, if any, became the leader. Implementing a test-and-set object is a closely related problem. In asynchronous shared memory, where processes communicate by writing to and reading from shared registers, deterministic wait-free solutions are impossible. However, using a randomized decision tree, leader election is possible to solve with \( O(\log n) \) worst-case expected step complexity.

Previously, the best lower bound was \( \Omega( \log n / \log k ) \), where \( k \leq n \) is the maximum number of processes that can be simultaneously poised to write to the same register. We prove an \( \Omega ( \log n / (\log \log n + \log Q) ) \) lower bound, where \( Q \leq k \) is the maximum number of different values that processes can be simultaneously poised to write to the same register. This show that any algorithm with \( o( \log n / \log \log n ) \) worst-case expected step complexity has \( \omega(\textrm{poly}\log n) \) value contention. It also implies a new lower bound that depends on register size. Our proof depends on a new specialized version of Turan's theorem.

This is joint work with Dan Alistarh and Alexander Fedorov and will appear at DISC 2025.

Host: Joan Boyar.

In 1977, Borodin and Kostochka conjectured that every graph with maximum degree \( \Delta \geq 9 \) is \( (\Delta-1) \)-colourable, unless it contains a clique of size \( \Delta \). In 1999, Reed confirmed the conjecture when \( \Delta\geq 10^{14} \). In this talk, we will propose different generalisations of this conjecture for digraphs, and prove the analogue of Reed's result for each of them.

This is joint work with Ararat Harutyunyan, Ken-ichi Kawarabayashi, and Gil Puig i Surroca.

Host: Anders Yeo.

Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an \( n \)-variate polynomial with bounded individual degree \( d \) and total degree \( D \), the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA '21], [Dell, Haak, Kallmayer, Wennmann; SODA '25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC '13] by a clever yet somewhat involved algorithm. We give a simple recursive algorithm that avoids heavy computer-algebraic machinery, and can be readily understood by researchers without specialized background.

This is joint work with Nick Fischer and Melvin Kallmayer.

Host: Lars Rohwedder.

In social choice problems, like voting and matching, the participating individuals (agents) are typically required to express their preferences over different alternative options by ranking them from best to worst. While this simplifies the preference elicitation process, it inevitably leads to low efficiency when aiming to choose an option that optimizes a cardinal objective such as the social welfare, since the underlying values of the agents for the alternative options (which are consistent to their reported rankings) remain virtually unknown. In this talk, we will explore the distortion framework for analyzing the efficiency of algorithms that make social decisions using incomplete information. In particular, we will focus on particular classes of query-enhanced algorithms which, besides the ordinal preferences of the agents, can also partially learn the values of the agents via (possibly inaccurate) queries, and then utilize all this information to make better decisions.

Host: Lars Rohwedder.

The field of Operations Research (OR) lies in the intersection between mathematics, computer science, data science, engineering, and business understanding. Its core element of optimization is, for example, used for planning and drawing insight for decision making, and it is naturally combined with modern technologies.

In this presentation, I will show three examples from my recent and ongoing research. The first example models and solves a combined truck and drone routing problem and illustrates the effect of different modeling approach. In the second example, I explain the idea of a method for solving (some) optimization problems without the use of Linear Programming, which is otherwise the basis of most OR methods for exact optimization. Resultingly, the algorithm operates in an integral space. This fundamental research project is at a prototype state. Finally, the third example is of applied nature and regards routing snow removal trucks during snowstorms. The idea is as follows: sensors are placed at selected places in the city to measure snowfall. Based on this, snowfall information is imputed for the whole city. Next, the information is used to predict near-future snowfall, and all that information is used for dynamic update of the snow trucks routes. Finally, the whole system is wrapped in a simulation framework, such that we can provide recommendations for where to place the sensors in the first place.

Host: Kim Skak Larsen.

Data structures are central to the design of efficient algorithms. The design of efficient data structures originates back to the 1960s with some of the earliest and still highly relevant results being the unbalanced binary search trees by Windley (1960), balanced binary search trees by Adelson-Velsky and Landis (1962), and the implicit priority queues by Williams (1964). Back then, the unit cost random access model (RAM) was a quite adequate model of a computer and counting the number of instructions done by an algorithm was a good measure for estimating its performance in practice. Since then, computer architectures continuously evolve and increase in complexity. In modern computers, performance bottlenecks are not only the number of instructions performed, but e.g. also the number of branch mispredictions, number cache faults (on various levels of the memory hierarchy), cache associativity, and TLB misses. Elevating the theoretical computational models to take these cost measures into account opened new directions for data structure design, e.g., the study of being optimal for multiple cost measures simultaneously, or if there is an inherent trade-off between the different cost measures. In this talk I will cover some of my contributions to classic data structure design, and data structures for hierarchical memory models.

Host: Kim Skak Larsen.

Today’s graph networks are complex, large and evolving. This necessitates the discovery of new graph algorithms and techniques which can be adapted to modern graphs. I will talk about my research, which is primarily concerned with designing algorithms for networks which are undergoing changes. I will focus on two problems: graph matching and edge coloring. Numerous practical applications have motivated the study of these classical graph problems in evolving graphs.

The problem of computing matchings on unweighted graphs in new models has received much attention. A natural generalization of this problem is the weighted setting, where edges have weights or cost functions. Unfortunately, there is a gap between the state-of-the-art for these two problems. In the first part of the talk, I will present a versatile framework which reduces the weighted setting to the unweighted setting.

In the second part of the talk, I will present my work on edge coloring, where my focus has been on analyzing a particular natural and simple algorithm that is conjectured to be optimal.

Host: Lars Rohwedder.

At least in some areas of algorithmics, there is some tension between theoreticians and practitioners. Algorithm engineers may criticize theoreticians for proposing algorithms with impressive asymptotic running times that are difficult or impossible to implement in a practically efficient manner. Conversely, theoreticians might view the contributions of algorithm engineering as lacking in theoretical depth.

This has prompted several major algorithms conferences to introduce applied tracks or co-located events - and sparked heated debate in others.

However, many landmark achievements have only been possible through a combination of theoretical insights and practical engineering. These include cases where implementation supported theoretical progress, such as in the proofs of the Kepler Conjecture and the Four Color Theorem, as well as cases where theory enabled remarkable algorithm engineering feats, such as the Concorde TSP solver.

In this talk, I will present examples from my own research where theory and practice have informed and reinforced each other. These include proving tight bounds on critical densities in covering and packing problems, and computing minimal samples to ensure coverage of feature interactions in testing configurable software systems.

Host: Lars Rohwedder.

Parameterized algorithms and approximation algorithms are well-established lines of research aiming to circumvent and further understand the complexity of NP-hard intractable problems. However, these techniques are not as popular when dealing with problems in P, since such problems already possess an "efficient solution". This classical view of efficiency is recently being challenged by both practical requirements (solving problems on big datasets) as well as fundamental barriers found within P (fine-grained complexity), thus increasing the need to develop and understand alternatives tools to classical complexity also within P.

In this talk, I will present a brief overview of this emerging research area: what is known and what we are still missing, what is similar and what is different to their use on NP-hard problems. I will use Minimum Chain Cover to illustrate how these techniques are effectively used to obtain efficient algorithms. A Minimum Chain Cover of a partially ordered set is a minimum-sized set of chains (pairwise comparable elements) whose union equals the entire set. Finding a Minimum Chain Cover has diverse applications ranging from scheduling to bioinformatics, where the graph sizes can reach the 100s of millions of vertices at the human pan-genome level, and thus applying the classical super-quadratic solutions becomes unfeasible.

Host: Lars Rohwedder.

Networks pervade every aspect of today’s life. This is one of the reasons why their design, management, and analysis is one of the most active areas of theoretical and empirical research in Computer Science and Operations Research. Survivable Network Design Problems (SNDPs) are a class of Graph Optimization problems focused on constructing networks that remain functional under failures or disruptions while minimizing the construction cost. These problems typically involve designing networks with specific connectivity guarantees, such as ensuring that a certain number of disjoint paths exist between critical nodes, even after the failure of links or nodes. SNDP finds important applications for instance in Transportation for creating resilient road or rail systems to handle disruptions such as accidents, Traffic jam or natural disasters. In this talk, we explore two classical and well-studied variants of survivable network design problems, presenting improved approximation algorithms for two families of these problems.

The first variant, known as kECCS (k-Edge-Connected Spanning Subgraph) or kVCSS (k-Vertex-Connected Spanning Subgraph), aims to find a minimum-size subgraph of a given graph that is k-edge-connected or k-vertex-connected.

The second variant, known as kECAP (k-Edge-Connectivity Augmentation Problem) or kVCAP (k-Vertex-Connectivity Augmentation Problem), considers a k-edge-connected (or k-vertex-connected) graph \( G \) and a set of additional edges, referred to as links. The objective is to select the smallest subset of links to add to \( G \), increasing its edge-connectivity (or vertex-connectivity) to \( k+1 \).

We discuss our methods and results, which advance the state-of-the-art in approximation algorithms for these fundamental problems.

Host: Lars Rohwedder.

Byzantine agreement is a fundamental problem in distributed computing that has numerous applications, for example, in cryptocurrencies. It considers a situation in which some constant fraction of the processes may behave maliciously. Despite this, the correct processes must agree on a value. In a system of \( n \) processes, if \( t < n/3 \) is the maximum number of malicious processes allowed and \( f \) is the actual number of malicious processes in an execution, then \( \min\{f+2,t+1\}\) rounds are necessary and sufficient to solve Byzantine agreement.

We consider a version of the Byzantine agreement problem in which each process is given a possibly incorrect prediction about which processes are correct and which are malicious. Different processes may be given different predictions. Can good predictions enable the correct processes to agree in fewer rounds, without causing them to take significantly more rounds when the predictions are bad? Suppose that \( B \) is the total number of incorrect bits in the prediction, that is, the total number of times correct processes are predicted to be malicious and malicious processes are predicted to be correct. We present a Byzantine agreement algorithm with predictions that takes \( O(\min\{B/n, f\}) \) rounds when \( B \in O(n\sqrt{n}) \) and \( O(f) \) rounds when \( B \in \omega(n\sqrt{n}) \). We also prove that every Byzantine agreement algorithm with predictions has an execution with \( f \) faults that takes at least \( \min\{f+2,t+1,B/(n-f) + 1, B/(n-t)\} \) rounds.

This is joint work with Naama Ben David, Ayaz Dzulfikar, and Seth Gilbert. It will appear at PODC 2025. No knowledge of distributed computing is necessary to understand the talk.

Host: Joan Boyar.

Differential Privacy has emerged as the gold standard for privacy in data analysis. Its main idea is to hide the influence of individual data inputs on the output of a given data analysis query, by adding carefully calibrated random noise. Though this field has been extensively studied within the last two decades, achieving accurate results while promising differential privacy remains challenging in a number of settings, for example when dealing with highly dimensional data like text documents.

In this talk, I will first give a short introduction to differential privacy. Then, I will explain the difficulties when dealing with multi-dimensional data inputs. Finally, I will present some recent results on differentially private document indexing, which show that combining strategies from string data structures and differential privacy for dynamic data lead to improved accuracy guarantees for differentially privately solving a range of problems on text documents, including frequent pattern mining.

This talk is based on joint work with Giulia Bernardini, Philip Bille, and Inge Li Gørtz.

Host: Kim Skak Larsen.

In various research fields, we capture the behavior of complex systems using randomized models and protocols. Such algorithms are typically conceived to facilitate stochastic methods to describe or rigorously explain aspects of the studied systems. We can even go a step further and use such model in practice, for instance, to validate analytical findings or to provide well-understood synthetic data. Graph generators are a common example of the latter and are an algorithmic challenge in their own right.

In this talk, we explore fundamental sampling techniques and demonstrate how they can serve as building blocks in graph generators and simulators. We will cover engineering aspects to obtain fast implementations on real machines with provable performance, and discuss how the targeted hardware informs algorithmic design decisions.

Host: Kim Skak Larsen.

Over the past several decades an exciting interplay has emerged between algorithms and the provability of mathematical statements, whereby short proofs give rise to efficient algorithms and vice-versa. This has led to state-of-the-art algorithms for many NP-hard problems. As well, it has enabled proof complexity – the study of what can be proven efficiently – to become a powerful tool for analyzing algorithms in both theory and practice. This has resulted in provable guarantees for a large number of important classes of practical algorithms including SAT solvers, integer programming solvers, and certain convex programs. These connections have also had an outsized impact on proof complexity, with tools from algorithms resolving a large number of important open questions in this area.

In this talk I will survey this interplay. I will describe how my co-authors and I have used it in order to resolve important open problems in a wide variety of areas; these include:

• Guarantees on the runtime of practical algorithms for solving integer programming problems,
• Trade-offs between the runtime and parallelizability of a variety of algorithms,
• Separations between complexity classes.

This talk is aimed at a broad computer science audience, and only a basic familiarity with complexity theory (P, NP, etc.) will be assumed.

Host: Kim Skak Larsen.

Let \( D \) be a directed graph with distinguished sets of sources \( S \subseteq V(D) \) and sinks \( T \subseteq V(D) \). A tripod in \( D \) is a subgraph consisting of the union of two \( S \)-\( T \)-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix.

I present our result that tripods in directed graphs exhibit the Erdős-Pósa property. More precisely, there is a function \( f\colon N \to N \) such that for every digraph \( D \) with sources \( S \) and sinks \( T \), if \( D \) does not contain \( k \) vertex-disjoint tripods, then there is a set of at most \( f(k) \) vertices that meets all the tripods in \( D \).

This is joint work with Marcin Briański, Karolina Okrasa and Michał Pilipczuk.

Host: Kim Skak Larsen.

Threshold signatures are a way to increase the security and robustness of authentication protocols, where a signing key is split into several shares, and a subset of the shares is needed to construct a signature, usually in a t-out-of-n manner where n is the total number of shares and t is the threshold required. This adds security since an adversary needs to get hold of t shares instead of only one to impersonate the signer, and it adds robustness since the signer is still able to construct a signature even if some of the shares are lost. The trade-off is that several parties now need to communicate to produce a signature, compared to the one-party setting where anyone holding the signing key can do this on their own, and many factors impact the efficiency of such schemes. There is a long line of research on threshold signature schemes based on factoring and discrete logarithms, but only recently have some works constructed threshold signatures from quantum-safe assumptions.

This talk will present a framework for threshold signature schemes from lattice assumptions, based on a recent publication at PQCrypto 2024 and follow-up work together with Kamil Doruk Gur (UMD), Patrick Hough (Oxford), Jonathan Katz (Google/UMD), and Caroline Sandsbråten (NTNU). The PQCrypto paper is available online: https://eprint.iacr.org/2023/1318.

Host: Joan Boyar.

Ph.D. defense.

Advisors: Joan Boyar, Kim Skak Larsen, Ruben Niederhagen, Claes de Vreese.

In this talk, we consider a broad class of algorithmic problems with an "additive flavor" such as computing sumsets, special cases of 3SUM and Subset Sum, and geometric pattern matching. These and many other problems can be solved efficiently for integer inputs, owed to the rich available tool set including bit-tricks, linear hashing, and the Fast Fourier Transform. However, as we lack similar tools for real numbers, there are significant gaps in the best-known running times for integer inputs versus for real inputs. The focus of this talk is a new technique towards closing this gap. Specifically, I will present a new algorithm for computing real sumsets, based on a surprising blend of algebraic ideas (linear recurrent sequences and coprime factorizations) with combinatorial tricks.

Host: Lars Rohwedder.

Coflow Scheduling models the problem of data exchange between various nodes in a shared network. It has been proven indispensable in improving the performance of common data exchange and distributed computing frameworks such as MapReduce, Spark, and Hadoop. The problem has enjoyed attention both from the theory community as well as the application side, with many works spanning the bridge between theory and practice. We present ongoing work.

Host: Lars Rohwedder.

I will look at selection rules that map any directed graph (without loops) to a subset of its vertices. A selection rule is impartial if the selection of a vertex is independent of its outgoing edges, and an optimal impartial rule is one that in any graph selects vertices with large indegrees. The idea is that vertices and edges represent individuals and nominations among individuals, and that we want to select highly nominated individuals without individuals having an influence on their own selection. I will discuss selection rules providing multiplicative and additive performance guarantees, corresponding impossibility results, and some open problems.

The talk is based on joint work with Noga Alon, Antje Bjelde, Javier Cembrano, David Hannon, Max Klimm, Ariel Procaccia, and Moshe Tennenholtz.

Host: Kevin Schewior.

Stochastic Boolean Function Evaluation (SBFE) problems have been studied for over 50 years. They have applications in a variety of areas, including database query optimization, artificial intelligence, quality testing, and networking. In an SBFE problem, we need to determine the value of a given Boolean function \( f \) on an initially unknown random input \( x=(x_1,\ldots,x_n) \). The only way to discover the value of an input variable \( x_i \) is to perform a "test" which incurs an associated cost. The test on \( x_i \) is \( 1 \) with given probability \( p_i \), and test outcomes are assumed to be independent. The SBFE problem is an optimization problem: Determine the optimal sequential order in which to perform the tests, in order to minimize the expected cost of determining the value of \( f \) on \( x \).

There are fundamental questions in this area which remain open. This talk is an introduction to SBFE problems, including discussion of basic results, recent work on approximation algorithms, and open questions.

Host: Kevin Schewior.

Given a graph \( G \), what is the length of the longest cycle of \( G \)? This problem generalizes the task of determining Hamiltonicity and is inherently at least as hard and important. To cope with its hardness, a line of research has focused on determining the length of the longest cycle in typical graphs, as opposed to atypical worst-case scenario ones. This can be interpreted as the study of long cycles in random graphs. In this talk, we will discuss recent results on the length of the longest cycle in the binomial random graph \( G(n,p) \). This talk is based on joint work with Alan Frieze.

Host: Lene M. Favrholdt.

Inspired by the practical challenges of coordinating jobs, machines, and time, the field of scheduling continues to influence fundamental algorithms research like few other fields do. Part of its popularity comes from the deep and versatile methods used and the many connections that scheduling has to other areas.

Focussing on such connections, I will present some contributions of my research towards resolving major gaps in our understanding of scheduling. Specifically, I will describe how recent progress in max-min fair allocation gives us hope to answer a long-standing question about makespan scheduling. Moreover, I will explain how the notoriously difficult flow time objective has become surprisingly manageable, in part due to insights from discrepancy theory.

Host: Lene M. Favrholdt.

Differential privacy is a rigorous privacy standard widely used in data analysis applications. Informally, a randomized algorithm is differentially private, if its output distribution does not depend much on any individual data entry in the input (consisting of many data entries). This implies that an adversary seeing only the output will not be able to recover any individual data entry of the input with certainty. The goal in differential privacy research is to design algorithms which are provably differentially private, while still giving approximately accurate results. From a theoretical point of view, the interesting question is to find the best possible privacy to accuracy tradeoff for any given problem.

In this talk, I will give a short general introduction to differential privacy. Then, I will talk about two research directions I have been working on: 1) Differential privacy for settings where the data changes over time, and we continuously want to answer queries with good accuracy while preserving differential privacy. 2) Differential privacy for strings, where the data is represented as a text or a sequence of symbols, and we want to answer queries about patterns in the sequence. I will conclude with some open problems and future research directions. The talk will be partially based on joint work with Monika Henzinger and A. R. Sricharan.

Host: Lene M. Favrholdt.

A graph class is a set of graphs that share some common structural property. They provide a systematic way of studying the complexity of problems that are computationally hard on general graphs. In this talk, I will focus on three properties: hereditary graph classes admit a characterization via forbidden induced subgraphs, tame graph classes have graphs with few minimal separators, and bounded width graph classes admit recursive well-structured decompositions. I will discuss how this field has evolved in the last decades, including my own work, and what are the current challenges.

Host: Lene M. Favrholdt.

A width measure typically provides a way of recursively disassembling graphs into smaller pieces, where the numerical width describes how complicated the interaction between the smaller parts was. Such so-called decompositions can be used to give divide-and-conquer like algorithms whose run time depends super-polynomially on the width of the decomposition rather than the size of the graph. In this talk, I will discuss several areas of algorithms and complexity through the lenses of width measures, focussing on my own contributions.

Host: Lene M. Favrholdt.

The talk will discuss the state of the art in semi-online load balancing, primarily with the added knowledge of optimum makespan. In this problem, \( m \) identical machines and the optimal makespan are given. The load of a machine is the total size of all the jobs assigned to it and the makespan is the maximum load of all the machines. Jobs arrive online and the goal is to assign each job to a machine while staying within a small factor (the competitive ratio) of the optimal makespan.

This problem is also known as online bin stretching. One long-standing open problem is to improve upon a basic lower bound of \( 4/3 \), currently the best-known one for any \( m \) larger than \( 8 \).

Semi-online load balancing has seen continuous research focus within the last ten years, and the talk will focus on recent efforts by several research teams, including some results from this year, yet to be published. In particular, we will discuss purely theoretical results as well as computer-aided efforts in proving lower and upper bounds, which are especially fruitful for this problem, and whose techniques, with some hope, can be adapted to other online problems.

References:

• Matej Lieskovský: Better Algorithms for Online Bin Stretching via Computer Search, 2022. https://arxiv.org/abs/2201.12393
• Antoine Lhomme, Olivier Romane, Nicolas Catusse, Nadia Brauner: Online bin stretching lower bounds: Improved search of computational proofs, 2022. https://arxiv.org/abs/2207.04931
• Sören Schmitt, Rob van Stee, Jiří Sgall, Matej Lieskovský, Martin Böhm: A Multi-Phase Algorithm for Bin Stretching with Stretching Factor below 1.5, 2022. Short abstract presented at MAPSP 2022.

Host: Kevin Schewior.