Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Eine Auswahl von Themen für Abschlussarbeiten

Nachfolgend sind einige Themenbereiche aufgeführt, zu denen am Lehrstuhl Komplexität und Kryptografie Bachelor- und Masterarbeiten betreut werden. Diese Liste ist keineswegs vollständig, insbesondere sind auch eigene Themenvorschläge gern willkommen. Manche der untenstehenden Themengebiete sind nur recht allgemein beschrieben und erlauben eine thematische Konkretisierung in verschiedener Weise, andere Themen betreffen spezifische Vorhaben. Bei Interesse nehmen Sie bitte zur weiteren Absprache Kontakt zu uns auf.

Themenvorschläge für Arbeiten bei Prof. Dr. Johannes Köbler:

Themenbereich A: Graphisomorphie und Weisfeiler-Leman-Algorithmus

Das Graphisomorphieproblem (GI) hat eine Sonderstellung in der Komplexitätstheorie. Es gehört zu den wenigen natürlichen Berechnungsproblemen in der Klasse NP, für die einerseits kein Algorithmus mit polynomieller Zeitschranke gefunden wurde und für die andererseits komplexitätstheoretische Ergebnisse vorhanden sind, die gegen eine NP-Vollständigkeit dieses Problems sprechen. Die derzeit beste obere Schranke für die Zeitkomplexität ist quasipolynomiell, d.h., O(n(log n)k), wobei k konstant ist (Babai 2016). Der Weisfeiler-Leman-Algorithmus ist eine rein kombinatorische Methode (mit tiefen algebraischen Charakterisierungen), die polynomielle Zeitschranken für das Isomorphieproblem auf vielen interessanten Graphenklassen ermöglicht und auch ein Bestandteil von Babais Algorithmus ist. In der Tat geht es nicht um einen einzigen Algorithmus, sondern um eine Klasse von Algorithmen, die auf ähnlichen Grundideen basieren. Wir nennen diesen allgemeinen, von Weisfeiler und Leman ausgehenden Ansatz "Kombinatorische Verfeinerung". Es ist eine wichtige Frage, auf welchen Graphenklassen die Kombinatorische Verfeinerung anwendbar ist. In diesen Kontext fallen die folgenden Themen:

A1: Kombinatorische Verfeinerung und symmetrische Graphen

Graphen mit vielen Automorphismen sind manchmal eine Herausforderung für die existierenden Isomorphie-Tester. Eine Quelle solcher Graphen sind endliche Gruppen, die zu sogenannten Cayley-Graphen führen. Sei G ein "durchschnittlicher" Cayley-Graph und H ein beliebiger Graph. Wie schwierig oder einfach ist es für die Kombinatorische Verfeinerung zwischen G and H zu unterscheiden? Das Konzept eines "durchschnittlichen" Cayley-Graphen ist nicht eindeutig und muss zuerst definiert und festgelegt werden. Das Thema lässt sich rein theoretisch oder auch teilweise als Programmierprojekt explorieren.

Literatur:

  • Josef Lauri, Raffaele Scapellato: Topics in Graph Automorphisms and Reconstruction Cambridge University Press, 2003
  • Sandra Kiefer: The Weisfeiler-Leman algorithm: an exploration of its power. ACM SIGLOG News 7(3): 5-27 (2020)
  • Martin Grohe, Daniel Neuen: Recent Advances on the Graph Isomorphism Problem. CoRR abs/2011.01366 (2020)

A2: Kombinatorische Verfeinerung und reguläre Graphen

Reguläre Graphen sind ebenfalls eine Herausforderung für die Isomorphie-Tester.
Es gibt eine ganze Hiererchie der unterschiedlichen Regularitätskonzepte.
Im Grunde heißt ein Graph regulär, wenn alle seinen Knoten gleich viele Nachbarn haben.
Ähnlich zum Thema A1 kann man "durchschnittliche" reguläre Graphen erforschen.
Eine andere, mehr "theoretische" Richtung ist es, mithilfe der vorhandenen Literatur
herauszufinden, für welche reguläre Graphen das Isomorphieproblem durch den klassischen
2-dimensionalen Weisfeiler-Leman-Algorithmus lösbar ist.

Literatur:

  • Sandra Kiefer:

    The Weisfeiler-Leman algorithm: an exploration of its power. ACM SIGLOG News 7(3): 5-27 (2020)

  • Martin Grohe, Daniel Neuen: Recent Advances on the Graph Isomorphism Problem. CoRR abs/2011.01366 (2020)
  • Bela Bollobas: Distinguishing vertices of random graphs. Annals of Discrete Mathematics 13:33-49, 1982.
  • Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier: Distance-Regular Graphs. Springer, 1989

A3: Identifizierung der Graphen mit Tinhofer-Eigenschaft

Tinhofer (1986) hat ein paradoxes kombinatorisches Verfahren entwickelt, das für überraschend viele Graphen eine effiziente Lösung des Isomorphieproblems bietet.
Wenn diese Methode ausgibt, dass zwei Graphen isomorph sind, dann stimmt das immer. Wenn wir aber eine negative Antwort bekommen, dann ist diese nicht immer zutreffend. Die Identifizierung derjenigen Graphen, bei denen das Verfahren korrekt funktioniert, ist eine spannende Frage.

Literatur:

  • Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky: Graph Isomorphism, Color Refinement, and Compactness. Computational Complexity 26(3): 627-685 (2017)

A4: Kombinatorische Verfeinerung und Gruppenisomorphie

Babais quasipolynomieller O(n(log n)k)-Algorithmus für das Graphisomorpie-Problem ist ein großer Erfolg von 2016. Für das Gruppenisomorphie-Problem ist aber die obere Schranke nlog n schon seit langem bekannt und ziemlich einfach. Das Gruppenisomorphieproblem ist auf Graphenisomorpie reduzierbar. Es ist also eine wichtige Frage, ob die Gruppenisomorphie in polynomieller Zeit lösbar ist. Der Weisfeiler-Leman-Algorithmus funktioniert für viele Graphenklassen sehr gut. Daher ist es eine natürliche Frage, welche Dimension der Weisfeiler-Leman-Algorithmus braucht, um Gruppenisomorphie entscheiden zu können. Es gibt interessante Literatur zu diesem Thema, sowohl mit positiven als auch negativen Ergebnissen. Zuallererst muss man sagen, dass die WL-Dimension für Gruppen zumindest drei unterschiedliche Definitionen hat. Es gibt aber auch ziemlich zugängliche Fragen, die man selbstständig erforschen kann.

Literatur:

  • Jendrik Brachter, Pascal Schweitzer: On the Weisfeiler-Leman Dimension of Finite Groups. LICS 2020: 287-300

Themenbereich B: Software für Forschung in Theoretischer Informatik

Auch in der Theorie ist es hilfreich, Software für das Finden von Gegenbeispielen, die Illustration von Varfahren oder schlicht zum intuitiven Verständnis von Algorithmen einzusetzen. Die folgenden Themen hängen eng mit Forschungsfragen des Lehrstuhls zusammen, bieten aber gleichzeitig die Möglichkeit auch Kentnisse aus der praktischen Informatik einfließen zu lassen:

B1: Eine praxisnahe Programmiersprache für LogSPACE (und weitere Klassen)

Ziel ist ein Werkzeug mit dem das Verhalten von Logspace-Algorithmen untersucht werden kann. Zudem kann das Implementieren Denkfehler aufdecken. Es gibt bereits WHILE-Spachen u.ä. für die die Äquivalenz zu LogSPACE bekannt ist, zudem kann LogSPACE in der deskriptiven Komplexitätstheorie durch Logiken beschrieben werden. Dieses Thema verfolgt etwas andere Ziele:

  • Ähnlichkeit zu / Teilmenge von existierender Programmiersprache (z.B. C/Python/Lua tec.)
  • Eingabe mindestens als Strings und (Paar von) Graphen
  • Orakel für Erreichbarkeit u.ä.
  • Zahlen mit fixer Bitlänge und solche mit log(Eingabelänge)-Bits
  • Separater Zeigertyp (z.B. für Adjazenzlisten)
  • Verschiedene Typen von Funktionen, die nur einmalig (d.h. sie löschen sich komplett vom Stack) oder rekursiv aufgerufen werden dürfen.
  • beweisbar LogSPACE, d.h. jedes gültige Programm soll nur logarithmischen Platz benötigen (unter Annahmen an Ursprungssprache)
  • für MSc-Arbeit erweiterbar auf LogCFL und/oder NC o.ä.

B2: Implementation von k-WL mit Ausgabe von Spielstrategien, Unterscheider-Formeln und kohärenten Konfigurationen

Viele Artikel nutzen mehr als eine Definition von Ununterscheidbarkeit durch den k-dimensionalen Weisfeiler-Leman-Algorithmus. Daher ist es sinnvoll, auch für Beispielgraphen zwischen den Formalismen übersetzen zu können. Für mindestens die drei Defintionen aus (Cai, Fürer und Immerman, 1992) und sogenannte koheränte Konfigurationen, soll das zu entwickelnde Programm passende Ausgaben liefern. Für 2-Personenspiele besteht die Ausgabe aus einer Funktion, die eine optimale Strategie des gewinnenden Spielers vollführt.

B3: Automatisches Zeichnen von k-WL-Ausgaben

Es gibt zahlreiche Algorithmen, die Graphen nach verschiedenen Kriterien "schön" in die Ebene zeichnen; siehe z.B. die Implementierungen in der graphdrawing-Bibliothek von tikz. Für die Analyse des Weisfeiler-Leman-Algorithmus mit 1 bis 3 Dimensionen bietet es sich an, dessen Ausgabe als gefärbten Graphen mit weiteren Anforderungen darzustellen, z.B.:

  • Knotenfarbklasen sollen nah bei beieinander sein
  • Kantenfarben von sich kreuzenden Klassen sollen hohen Kontrast haben
  • Bei 3-WL haben Dreiecke Farben - wie stellt man diese geeignet dar?
  • Die Farbwahl der Knoten soll die Runde der Trennung wiedergeben, d.h. z.B. rot/schwarz wurde in Runde 1 unterschieden, rot/orange in Runde 3

Themenbereich C: Graphisomorphie für eingeschränkte Graphklassen

C1: Teilklassen von chordalen Graphen

Graphisormorphie ist auf chordalen genauso schwer wie auf allgemeinen Graphen. Chordale Graphen kann man u.a. als Schnittgraphen von Teilbäumen eines Baums definieren, d.h. zwei Knoten eines chordalen Graphen sind verbunden, falls sich die dazugehörigen Teilbäume schneiden. Damit sind sie eine Verallgemeinerung von Intervallgraphen, für die seit langem bekannt ist, dass Graphisomorphie auf ihnen in Linearzeit zu entscheiden ist. Seit kurzem gibt es FPT-Algorithmen für chordale Graphen mit beschränkter Leafage (Blättrichkeit), d.h. die Anzahl der Blätter im Hauptbaum ist durch eine Zahl k beschränkt. Hier kann man untersuchen, ob (wie bei Intervallgraphen) auch Graphsisomorphie in Teilklassen von P (z.B. LOGSPACE) möglich ist oder das Erkennungsproblem für Graphen mit beschränkter Leafage betrachten. Zudem lassen sich auch andere Einschränkungen von chordalen Graphen betrachten.

Literatur:

  • V. Arvind, R. Nedela, I. Ponomarenko, P. Zeman: Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable.(arxiv.org/abs/2107.10689)
  • D. Ağaoğlu Çağırıcı, P. Hliněný: Isomorphism Testing for T-graphs in FPT. (arxiv.org/abs/2111.10910)

Themen für Arbeiten bei PD Dr. Wolfgang Kössler:

Berechnung mehrdimensionaler Wahrscheinlichkeiten

In vielen statistischen Fragestellungen taucht eine mehrdimensionale Normalverteilung auf, deren Wahrscheinlichkeiten Mehrfachintegrale sind. Es sind verschiedene numerische Algorithmen hinsichtlich ihrer Komplexität zu analysieren und zusätzlich Monte Carlo Algorithmen (klassisch, Importance Sampling) zu implementieren.
Die Verfahren sind auf konkrete Beispiele mit (mehr oder weniger) vorgegebenen Korrelationskoeffizienten anzuwenden.
 

 

U-Statistiken

Eine interessante Klasse von Test- und Schätzstatistiken sind U-Statistiken, bei denen aus den Stichproben jeweils Teilstichproben von bestimmtem (festen) Umfang k gezogen werden.
Der Berechnungsaufwand ist größer als bei gewöhnlichen Statistiken. Der Aufwand ist, in Abhängigkeit von den Stichprobenumfängen und von k abzuschätzen.
Weiterhin sind effiziente Algorithmen zu implementieren, vorzugsweise in der Statistiksprache SAS. Fortran oder Java sind ebenfalls möglich.
 

 

Extreme Ereignisse

Zur Modellierung extremer Ereignisse, wie z.B. schlechter Qualität, verwendet man (auch) die verallgemeinerte Pareto-Verteilung. Die Parameter werden nach der Maximum-Likelihood-Methode geschätzt. Die Schätzungen sind asymptotisch normalverteilt, aber eben nur "asymptotisch". Für kleine und mittlere Stichprobenumfänge müssen andere Verteilungen an die Parameterschätzung angepasst werden, z.B. die lognormal-Verteilung.

Folgende Fragestellungen sind experimentell zu lösen:

  1. Welche (bivariaten) Verteilungen approximieren die Verteilung der Parameterschätzungen besser als die Normalverteilung.
  2. Welche Verteilung hat der geschätzte Ausschussanteil?
  3. Maximum-Likelihood-Schätzungen sind globale Maxima von (i.A. nichtlinearen) Funktionen mit evtl. mehreren lokalen Maxima. Evtl. lassen sich Optimierungsprogramme erstellen, die auf die spezielle Likelihood-Funktion der verallgemeinerten Pareto-Verteilung zugeschnitten sind.

 

Robuste Kontrollkarten

In der statistischen Qualitätskontrolle verwendet man zur Überwachung des (Produktions-) Prozesses sogenannte Kontrollkarten (z.B. Shewart, Cusum, EWMA), die jedoch stark von der angenommenen Normalverteilung des Prozesses abhängen. Es stellt sich hier die Frage, ob und wie hier robustere Methoden angewendet werden können.