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.