Sebastian Berndt

Sebastian Berndt

Postdoc in IT security

University of Lübeck


Sebastian Berndt is a postdoc at the Institute for IT Security led by Prof. Dr. Thomas Eisenbarth at the University of Lübeck. His research interests revolve around intractable problems. On the one hand, he applies these problems to cryptography and steganography to enable secure communication. On the other hand, he tries to solve them with approaches such as approximation algorithms or fixed-parameter-tractability.

List of Coauthors

I had the pleasure to work with very talented researchers. In alphabetical order, they are

Max Bannach, Valentin Dreismann, Thorsten Ehlers, Thomas Eisenbarth, Leah Epstein, Kilian Grage, Klaus Jansen, Kim-Manuel Klein, Ingmar Knof, Alexandra Lassota, Asaf Levin, Maciej Liśkiewicz, Matthias Lutter, Marten Maack, Matthias Mnich, Dirk Nowotka, Malin Rau, Rüdiger Reischuk, Lars Rohwedder, Okan Seker, Malte Skambath


  • Cryptography
  • IT security
  • Algorithms (Parameterized, Approximation, Online)


  • PhD in Computer Science (summa cum laude), 2018

    University of Lübeck

  • M.Sc. in Computer Science, 2012

    Kiel University

  • BSc in Computer Science, 2010

    Kiel University

Recent Posts

MFCS 2020

Our paper Solving Packing Problems with Few Small Items Using Rainbow Matchings was accepted at MFCS 2020.

PACE 2020

We participated in the PACE 2020 treedepth challenge and got place 4 out of 15 in the exact track and place 5 out of 10 in the heuristic track.


Two new preprints are available. In the first paper, we investigate the vertices of the integer hull, the integer analogues of basic feasible solutions. We either match or improve the best known upper bounds on their number via surprisingly simple probabilistic methods. In the second paper, we show how to provably protect MPC-in-the-head protocols against sidechannel attacks. To illustrate this approach, we secured the Picnic signature scheme.


I moved to the Institute for IT Security in Lübeck.


I will participate in the Dagstuhl Seminar 20132 The Renaissance of Information Hiding, which has been moved due to COVID-19.

Recent Publications

Quickly discover relevant content by filtering publications.

Online Bin Covering with Limited Migration (ESA 2019)

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years.

This is motivated …

Robust Online Algorithms for Certain Dynamic Packing Problems (WAOA 2019)

Online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are …

Positive-Instance Driven Dynamic Programming for Graph Searching (WADS 2019)

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 …

SAT-Encodings of Tree Decompositions (SAT 2018)

We suggest some benchmarks based on a propositional encoding of tree decompositions of graphs

Fully Dynamic Bin Packing Revisited (Math. Prog. 2018)

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously …