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.