Im letzten Jahrzehnt gab es immensen Fortschritt und Wachstum in den Bereichen der Künstlichen Intelligenz, des Data Mining und des Maschinellen Lernens. Diese Entwicklung wurde durch spezialisierte neue Hardware, die immer größere Verfügbarkeit von Daten und Durchbrüche bei der Entwicklung von Algorithmen, die Muster in Daten finden und ausnutzen, ermöglicht. Obwohl wir uns in der Praxis täglich vom großen Erfolg dieser Algorithmen überzeugen können, ist unser theoretisches Verständnis von ihnen weiterhin eingeschränkt. Allerdings wären formale Garantien für diese Algorithmen höchst wünschenswert, weil sie wichtige Einblicke in die Stärken und die Grenzen dieser Algorithmen erlauben. Das Ziel dieser Dissertation ist es, die Kluft zwischen Theorie und Praxis zu verkleinern. Dafür entwickeln wir Algorithmen, die beweisbar Muster in Daten finden und ausnutzen. Die Zusammenfassung der Ergebnisse ist wie folgt: • Beweisbar Muster finden: Wir entwickeln Algorithmen, die beweisbar eine Menge von versteckten Clusterns aus bipartiten Zufallsgraphen extrahieren. Eine Anwendung von diesem Problem ist die Analyse von Onlineshopping-Daten, in denen Gruppen von Produkten gesucht werden, die häufig gemeinsam gekauft werden, und Gruppen von Kund⋅innen, die ähnliche Produkte kaufen. Wir präsentieren den ersten Algorithmus, der beweisbar winzige versteckte Cluster finden kann. Dieses Resultat liefert eine theoretische Begründung für den Erfolg bereits existierender heuristischer Methoden, die in der Praxis verwendet werden. Außerdem präsentieren wir den ersten Datenstromalgorithmus, der nur zwei Iterationen über die Knoten eines bipartiten Graphen vornimmt und anschließend eine Menge an versteckten Clustern ausgibt. Der Algorithmus skaliert auf viel größere Daten als bekannte Methoden. • Verstehen der Komplexität des Musterfindens: Wir betrachten die Komplexität häufig verwendeten Subroutinen von Data Mining-Algorithmen und erhalten neue Härteresultate. Für die approximative Berechnung der Anzahl der Dreiecke in einem Graphen und für die Approximation der Häufigkeit von Itemsets in transaktionalen Datenbanken zeigen wir, dass existierende Algorithmen, die auf zufälligen Stichprobenverfahren beruhen, nicht signifikant verbessert werden können, außer gängige Hypothesen der Komplexitätstheorie sind falsch. Außerdem präsentieren wir eine Hierarchie der Enumerationskomplexität von mehreren Maximal Frequent Pattern Mining-Problemen und wir bestimmen eine Bedingung, unter der diese Hierarchie zusammenbricht. • Beweisbar Muster ausnutzen: Wir formulieren ein theoretisches Modell, das die Struktur von Mustern in realen Kommunikationsnetzwerken abbildet. Wir entwickeln Algorithmen, die die Muster in den Daten ausnutzen und damit den Datenverkehr im Netzwerk reduzieren. Wir beweisen, dass der kompetitive Faktor unserer Algorithmen asymptotisch optimal ist. Um unsere Resultate zu erhalten, verwenden wir die beyond worst-case Analyse: Anstatt von worst-case Eingaben für unsere Algorithmen auszugehen, nehmen wir an, dass die Eingabedaten die Eigenschaften von praktischen Datensätzen erfüllen.

In the last decade, there has been immense progress and growth in the fields of artificial intelligence, data mining and machine learning. This development was enabled by specialized new hardware, the ever-larger availability of data and breakthroughs in the development of algorithms that find and exploit patterns in the data. While these methods are known to be extremely successful in practice, our theoretical understanding of them is still limited. However, formal guarantees for these algorithms are highly desirable, because they yield important insights into the strengths and the limitations of these algorithms. In this thesis, we make an effort to narrow the gap between theory and practice. To this end, we develop algorithms for provably finding and exploiting patterns in data. The results are summarized as follows: • Provably Finding Patterns: We provide algorithms that provably extract a set of planted clusters from random bipartite graphs. This problem has applications, for example, in the analysis of online shopping data, where one wishes to identify groups of products that are frequently bought together and groups of customers who purchase similar products. We present the first algorithm which can provably extract tiny planted clusters. This result provides a theoretical justification for the success of existing heuristic methods that are used in practice. We further present the first streaming algorithm which, after two passes over a bipartite graph, returns a set of planted clusters and which scales to much larger datasets than existing methods. • Understanding the Complexity of Finding Patterns: We study the computational complexity of frequently-used subroutines of data mining algorithms and provide new hardness results. We show that for approximately computing the number of triangles in a graph and for approximating the support of itemsets in transactional databases, existing random sampling algorithms cannot be significantly improved unless popular conjectures in computational complexity are false. Furthermore, we present a hierarchy of the enumeration complexity of several maximal frequent pattern mining problems and we provide a condition under which this hierarchy collapses. • Provably Exploiting Patterns: We formulate a theoretical model that captures the structure of the patterns in real-world communication networks. We provide algorithms that reduce the network traffic by exploiting these patterns and we show that the competitive ratios obtained by our algorithms are asymptotically optimal. To obtain our results, we use beyond worst-case analysis, i.e., instead of considering worst-case inputs for our algorithms, we consider inputs that satisfy the properties of real-world datasets.