In his thesis "Provably Finding and Exploiting Patterns in Data", supervised by Prof. Dr. Monika Henzinger, Stefan Neumann develops algorithms for data mining problems and even proves for some of them that they cannot be solved better. The methodology of the work follows the "beyond worst-case analysis", in which the properties of real data are mathematically modelled. Then, these assumptions are exploited to derive provable guarantees for the efficiency and solution quality of the developed algorithms. This is in stark contrast to conventional methods that are successful in practice but whose mode of operation is poorly understood from a theoretical perspective. Since the algorithms of the dissertation have provable guarantees, Dr Neumann's research constitutes an important contribution to the formal understanding of mathematical problems in machine learning. For several of the results obtained, it is proven that they are optimal, meaning that they cannot be improved. In addition to their theoretical relevance, the research results also provide important practical insights: Stefan Neumann proposes new algorithms that build on the mathematical ideas but can also be used practically. To achieve these results, the doctoral student links different areas of computer science, such as complexity theory, online algorithms and data mining. The work is also convincing due to complex proofs that reveal a high technical quality and provides an important contribution to the basic understanding of artificial intelligence problems.

Stefan Neumann co-authored 15 articles during his PhD, 13 of which have already been published peer-reviewed. Five chapters of the dissertation have already been published at the world's leading conferences in their respective fields.