8 citations · 11 across the 6 of their papers we have counts for
15 papers
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
Sebastian Berndt, Hauke Brinkop, Klaus Jansen +2
Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs d…
Dash: Accelerating Distributed Private Convolutional Neural Network Inference with Arithmetic Garbled Circuits
Jonas Sander, Sebastian Berndt, Ida Bruhns +1
The adoption of machine learning solutions is rapidly increasing across all parts of society. As the models grow larger, both training and inference of machine learning models is i…
Util::Lookup: Exploiting key decoding in cryptographic libraries
Florian Sieck, Sebastian Berndt, Jan Wichelmann +1
Implementations of cryptographic libraries have been scrutinized for secret-dependent execution behavior exploitable by microarchitectural side-channel attacks. To prevent unintend…
Load Balancing: The Long Road from Theory to Practice
Sebastian Berndt, Max A. Deppert, Klaus Jansen +1
There is a long history of approximation schemes for the problem of scheduling jobs on identical machines to minimize the makespan. Such a scheme grants a -approximation sol…
Robust Online Algorithms for Dynamic Choosing Problems
Sebastian Berndt, Kilian Grage, Klaus Jansen +2
Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous work…
Tightness of Sensitivity and Proximity Bounds for Integer Linear Programs
Sebastian Berndt, Klaus Jansen, Alexandra Lassota
We consider ILPs, where each variable corresponds to an integral point within a polytope , i. e., ILPs of the form $\min\{c^{\top}x\mid \sum_{p\in\mathcal P\cap \mathb…
Solving Packing Problems with Few Small Items Using Rainbow Matchings
Max Bannach, Sebastian Berndt, Marten Maack +4
An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been st…
New Bounds for the Vertices of the Integer Hull
Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein
The vertices of the integer hull are the integral equivalent to the well-studied basic feasible solutions of linear programs. In this paper we give new bounds on the number of non-…
Robust Online Algorithms for Dynamic Problems
Sebastian Berndt, Valentin Dreismann, Kilian Grage +2
Online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are essential in the design of competitive algorithms for…
Positive-Instance Driven Dynamic Programming for Graph Searching
Max Bannach, Sebastian Berndt
Research on the similarity of a graph to being a tree - called the treewidth of the graph - has seen an enormous rise within the last decade, but a practically fast algorithm for t…
Online Bin Covering with Limited Migration
Sebastian Berndt, Leah Epstein, Klaus Jansen +3
Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is ofte…
Practical Access to Dynamic Programming on Tree Decompositions
Max Bannach, Sebastian Berndt
Parameterized complexity theory has lead to a wide range of algorithmic breakthroughs within the last decades, but the practicability of these methods for real-world problems is st…
On the Gold Standard for Security of Universal Steganography
Sebastian Berndt, Maciej Liśkiewicz
While symmetric-key steganography is quite well understood both in the information-theoretic and in the computational setting, many fundamental questions about its public-key count…
Algorithm Substitution Attacks from a Steganographic Perspective
Sebastian Berndt, Maciej Liskiewicz
The goal of an algorithm substitution attack (ASA), also called a subversion attack (SA), is to replace an honest implementation of a cryptographic tool by a subverted one which al…
Fully Dynamic Bin Packing Revisited
Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein
We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, t…