19. November 2020

Abstract

In a typical introductory course on theoretical computer science one learns that polyno-mial time reductions are used to show that a computational problem cannot be solved in polynomial time (unless P=NP). It seems that beyond this plain NP-hardness conclusion there is not much to be learned from such reductions; they seem to merely serve as justification to actually start studying the problem at hand since it is officially classified as being hard.

This talk will remedy the false reputation of reductions as blunt instruments for NP-hard-ness. Reductions in fact yield powerful connections between seemingly unrelated prob-lems that reveal useful similarities. To support this claimed power of reductions, we will look at examples from several application areas which illustrate the different types of information that can be transferred. With the help of appropriate reductions it is possible to inherit approximation results (approximation-preserving reductions) or to derive strict specific running time lower bounds (fine-grained reductions). Further, reductions can give us insight into the limits of particular algorithmic strategies but also translate successful strategies from one problem to another.

Short CV

Katrin Casel is a postdoctoral researcher in the Algorithm Engineering group at the Hasso Plattner Institute. The main focus of her research are parameterized and approximation algorithms, especially the rigorous analysis of such approaches and their limits. For a more detailed study of computational lower bounds, she recently started working with methods from fine-grained complexity.

After receiving a Diplom (former German M.Sc. degree) both in Applied Mathematics and Computer Science from the University of Trier in 2013, she spent three months as visiting researcher at the University of Newcastle. She then worked at the University of Trier on a DFG project on parameterized approximation, where she obtained her Ph.D. in Com-puter Science in 2018 for her study of parameterized approximation methods for balanced clustering problems. Right after receiving her Ph.D she joined the Hasso Plattner Institute in 2018.

Host: Prof. Dr. habil. Katharina Hölzle, MBA