In der Dissertation “Provably Finding and Exploiting Patterns in Data”, betreut von Prof. Dr. Monika Henzinger, entwickelt Stefan Neumann Algorithmen für Probleme des Data Minings und beweist für einige sogar, dass sie nicht besser gelöst werden können. Die Methodik der Arbeit folgt der “beyond worst-case Analyse”, bei der die Eigenschaften von realen Daten mathematisch modelliert werden. Anschließend werden diese Annahmen ausgenutzt, um beweisbare Garantien für die Effizienz und die Lösungsqualität der entwickelten Algorithmen herzuleiten. Dies steht im starken Kontrast zu herkömmlichen Verfahren, die zwar in der Praxis erfolgreich sind, deren Wirkweise aber aus theoretischer Sicht unzureichend verstanden wird. Da die Algorithmen der Dissertation beweisbare Garantien besitzen, bildet Dr. Neumanns Forschung einen wichtigen Beitrag zum formalen Verständnis der mathematischen Probleme im Maschinellen Lernen. Für mehrere der erzielten Resultate wird bewiesen, dass sie optimal sind, das heißt, sie können nicht verbessert werden. Neben ihrer theoretischen Relevanz liefern die Forschungsergebnisse auch wichtige praktische Erkenntnisse: Stefan Neumann schlägt neue Algorithmen vor, die auf den mathematischen Ideen aufbauen, aber auch praktisch einsetzbar sind. Um diese Resultate zu erzielen, verknüpft der Dissertant verschiedene Bereiche der Informatik, wie Komplexitätstheorie, Online Algorithmen und Data Mining. Die Arbeit überzeugt zudem durch komplexe Beweise, die eine hohe technische Qualität offenbaren und liefert einen wichtigen Beitrag zum Grundlagenverständnis von Problemen der Künstlichen Intelligenz.

Stefan Neumann war während der Zeit seiner Promotion Co-Autor von 15 Artikeln, wovon 13 bereits peer- reviewed veröffentlicht sind. Fünf Kapitel der Dissertation wurden bereits bei den weltweit führenden Konferenzen auf ihren jeweiligen Gebieten veröffentlicht.