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.

Host: Joan Boyar.

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.