4/6 2025, 10:30, U174
Phillip Keldenich, Technische Universität Braunschweig Theory Meets Practice: Computer-Aided Proofs and Algorithm Engineering |
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.
28/5 2025, 14:00, U174
Manuel Cáceres, Aalto University Efficient algorithms for intractable problems in 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.
26/5 2025, 13:00, IMADA Conference Room
Afrouz Jabal Ameli, Eindhoven University of Technology Towards Efficient Design of Resilient Networks |
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.
13/5 2025, 14:15, CP3 Meeting Room
Faith Ellen, University of Toronto Byzantine Agreement with Predictions |
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.
29/4 2025, 14:15, CP3 Meeting Room
Teresa Anna Steiner, University of Southern Denmark Differential Privacy for 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.
3/4 2025, 9:00, IMADA Conference Room
Manuel Penschuck, Goethe-Universität Frankfurt Selected Samples of Practical and Scalable Sampling Algorithms |
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.
21/3 2025, 13:45, zoom
Noah Fleming, Memorial University Connecting Proofs and Algorithms |
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.
Host: Kim Skak Larsen.
13/3 2025, 9:00, zoom
Meike Hatzel, Institute for Basic Science, Daejeon, South Korea Erdős-Pósa property of tripods in directed graphs |
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.
18/2 2025, 10:15, IMADA Conference Room
Tjerand Silde, Norwegian University of Science and Technology Quantum-Safe Threshold Signatures |
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:
Host: Joan Boyar.
https://eprint.iacr.org/2023/1318
.
17/2 2025, 13:15, IMADA Conference Room
Simon Erfurth, University of Southern Denmark Slightly Homomorphic Digital Signatures and Privacy Preserving Folding Schemes. |
Host: Joan Boyar.
11/2 2025, 14:15, IMADA Meth. Lab.
Nick Fischer, Institute for Computer Science, Artificial Intelligence and Technology Sumsets, 3SUM, Subset Sum: Now for Real! |
Host: Lars Rohwedder.
4/2 2025, 14:15, IMADA Conference Room
Leander Schnaars, Technical University of Munich Coflow Scheduling |
Host: Lars Rohwedder.
19/11 2024, 14:15, IMADA Meth. Lab
Felix Fischer, Queen Mary University of London Optimal Impartial Selection |
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.
21/5 2024, 14:15, IMADA Seminar Room
Lisa Hellerstein, New York University Stochastic Boolean Function Evaluation: Progress and Challenges |
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.
13/5 2024, 10:30, IMADA Conference Room
Michael Anastos, Institute of Science and Technology Austria Long Cycles in Sparse Random Graphs |
Host: Lene M. Favrholdt.
29/4 2024, 12:30, IMADA Seminar Room
Lars Rohwedder, Maastricht University The Many Facets of Scheduling |
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.
24/4 2024, 10:30, IMADA Seminar Room
Teresa Anna Steiner, Technical University of Denmark Differential Privacy for Dynamic Data and Strings |
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.
23/4 2024, 10:30, IMADA Conference Room
Paloma Thomé de Lima, IT University of Copenhagen Algorithms Meet Structure: Hereditary, Tame and Bounded Width Graph Classes |
Host: Lene M. Favrholdt.
11/4 2024, 10:30, IMADA Conference Room
Lars Jaffke, University of Bergen Exploring Algorithmic Graph Theory through Width Measures |
Host: Lene M. Favrholdt.
15/11 2023, 14:15, U161
Martin Böhm, University of Wrocław Semi-Online Load Balancing: What's new in 2023? |
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.