Studien- und Abschlussarbeiten

Datenbanken sind häufig inkonsistent, d. h. sie verletzten gegebene Integritätsbedingungen. Aus diesem Grund ist man an Reparaturen interessiert. Allgemein geht es beim Problem des sogenannten Consistent Query Answering (CQA) darum, dass in Bezug auf eine gegebene Anfrage (Query) alle Reparaturen sich bzgl. Q konsistent verhalten sollen. Dieses Problem ist coNP-vollständig und daher nicht effizient lösbar (wenn P und NP nicht gleich sind). Eine möglicher Ansatz für solche Probleme bietet die parametrische Komplexitätstheorie. In diesem Kontext [1] wurde eine Graphenrepräsentation entwickelt für die effiziente Algorithmen gefunden wurden, sofern die Baumweite konstant ist.

In der Arbeit soll aufbauend auf einer vorherigen Bachelorarbeit [2] ausführliche Simulationen durchgeführt werden. Hierbei sollen für Testdatenbanken sinnvolle Integritätsbedingungen entworfen werden, mit Anfragen bestückt und anschließend die zugehörigen Solution-Conflict-Hypergraphen berechnet werden. Im nächsten Schritt sollen Baumweiten [3] hiervon berechnet werden. 

Literatur: 

[1] Teemu Hankala, Miika Hannula, Yasir Mahmood, Arne Meier: Parameterised Complexity of Consistent Query Answering via Graph Representations. CoRR abs/2412.08324 (2024), https://arxiv.org/abs/2412.08324
[2] Carlotta Peckmann: Baumweite in Datenbanken, 2024. Bachelorarbeit.
[3] Hisao Tamaki: Computing Treewidth via Exact and Heuristic Lists of Minimal Separators. SEA² 2019: 219-236, https://github.com/twalgor/tw

Viele Anfragen an relationale Datenbanken sind sogenannte "conjunctive queries", zu denen auch einfache SQL-Anfragen gehören. Daher ist das Beantworten dieser "conjunctive queries" ein zentrales Problem in der Datenbanktheorie. Die "fine-grained complexity" beschäftigt sich mit der Analyse von Laufzeiten innerhalb großer Komplexitätsklassen wie P. Mit ihrer Hilfe können, unter Annahme bestimmter Hypothesen, genauere untere Schranken für Probleme aufgezeigt werden (zum Beispiel super-lineare Laufzeiten).

Es soll ein Überblick über die Schnittstelle zwischen "conjunctive queries" und der "fine-grained complexity" erarbeitet werden.

Literatur:

• Stefan Mengel: Lower Bounds for Conjunctive Query Evaluation. CoRR abs/2506.17702 (2025) (https://arxiv.org/abs/2506.17702).

In der Schaltkreistheorie sind insbesondere für den Fall monotoner Schaltkreise (ohne Negationsgatter) fundamentale untere Schranken bekannt. Eine neuartige Anwendung einer Technik aus der Kommunikationskomplexität hat zu beträchtlichen neuen Ergebnissen geführt, die in dieser Arbeit zusammengefasst werden sollen.

Literatur:

• Susanna F. de Rezende et al., Lifting with simple gadgets and applications to circuit and proof complexity. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS ’20), November 2020. doi:10.1109/focs46700.2020.00011.

• Ankit Garg et al., Monotone circuit lower bounds from resolution. Theory of Computing, 16(13):1–30, 2020. Preliminary version in STOC ’18. doi:10.4086/toc.2020.v016a013.

In der Kommunikationskomplexität untersucht man den Kommunikationsaufwand, der erforderlich ist, um ein Problem zu lösen, wenn die Eingabe für das Problem auf zwei oder mehr Parteien verteilt ist. Ein Überblick über das Gebiet soll erarbeitet werden.

Literatur:

• Anup Rao, Amir Yehudayoff, Communication complexity and applications, Cambridge, 2020.  
• Eyal Kushilevitz, Noam Nisan, Noam, Communication complexity. Cambridge, 2006.

Die Klasse TFNP besteht aus den totalen Funktionen, die in nichtdeterministischer Polynomialzeit berechnet werden können. Das heißt, es handelt sich um die Klasse der Funktionsprobleme, für die garantiert eine Antwort vorliegt, und diese Antwort kann in Polynomialzeit überprüft werden. Die Abkürzung TFNP steht für „Total Function Nondeterministic Polynomial“. Die wesentlichen komplexitätstheoretischen Resultate über diese Klasse sollen zusammengetragen werden.

Literatur:

• Nimro d Megiddo and Christos H Papadimitriou, A Note on Total Functions Existence Theorems and Computational Complexity, https://doi.org/10.1016/0304-3975(91)90200-L, 1989.
• John Fearnley et al., CLS: New Problems and Completeness, https://arxiv.org/pdf/1702.06017, 2017.

Ein Lifting-Theorem ist ein Satz, der eine untere Schranke in einem schwachen Berechnungsmodell in eine untere Schranke in einem starken Modell übersetzt. Ein Überblick über verschiedene derartige Resultate soll erarbeitet werden.

Literatur:

• Susanne F. de Rezende et al., KRW Composition Theorems via Lifting, https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9317931, 2020.

In der Informatik lassen sich viele Probleme so modellieren, dass aus gewissen Basiselementen durch festgelegte Operationen (Abschlussoperationen) neue Elemente generiert werden. Für verschiedene Spezialfälle ist die genaue Komplexität der Aufzählung aller generierten Elemente bekannt. Die Resultate sollen wiedergegeben werden.

Literatur:

• Arnaud Mary ORCID und Yann Strozecki, Efficient enumeration of solutions produced by closure operations, dmtcs.episciences.org/5549, 2019

Matroide sind mathematische Strukturen, in denen Abhängigkeiten zwischen Elementen herrschen. Sie finden Anwendung in vielen Bereichen der Informatik, insbesondere der kombinatorischen Optimierung und Graphentheorie. Die Existenz von Greedy-Algorithmen für algorithmische Probleme kann oft auf eine zugrundeliegende Matroid-Struktur zurückgeführt werden.  
In diesem Bereich sind einige Abschlussarbeiten zu vergeben. Mögliche Themen sind:

1. Darstellung der Grundzüge der mathematischen Matroid-Theorie
2. Darstellung der Zusammenhänge zwischen Matroiden und Greedy-Algorithmen
3. Darstellung und Analyse beispielhafter Algorithmen, bspw. das Berechnen von Spannbäumen oder das Finden aller Kreise eines Graphen.

Literatur:

• D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. Band 8). Academic Press, London, New York, San Francisco 1976.  
• Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall, Englewood Cliffs (NJ) 1982.  
• L. Khachiyan, On the Complexity of Some Enumeration Problems for Matroids, https://doi.org/10.1137/S0895480103428338, 2006.

Die Klasse ETR (oder auch ∃R) besteht aus allen Sprachen, die sich auf die Frage der Gültigkeit von Formeln über den reellen Zahlen mit Existenzquantor reduzieren lassen. Die Klasse ist zwischen NP und PSPACE angesiedelt. Sie enthält viele kontinuierliche geometrische Probleme, die sich als Verallgemeinerungen von NP-vollständigen Sprachen auf den reellen Grundbereich ergeben. Strukturelle Beziehungen und Vollständigkeitsresultate sollen zusammengefasst und dargestellt werden.

Literatur:

• Mikkel Abraham et al., The Art Gallery Problem is ∃R-complete, https://dl.acm.org/doi/10.1145/3486220, 2021.
• Saugata Basu et al., Existential Theory of the Reals. In: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol 10. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-33099-2_14

Hierarchien von Komplexitätsklassen, deren Ressourcenschranke nicht elementar ist, d.h. schneller wächst als jeder Turm von Exponentialfunktionen fester Höhe, werden in einer Arbeit von S. Schmitz untersucht. Eine neue Komplexitätsklasse TOWER spielt eine wichtige Rolle. Die Ergebnisse sollen zusammengefasst werden.

Literatur:

• Sylvain. Schmitz, Complexity Hierarchies beyond Elementary, https://doi.org/10.1145/2858784.

Das von Ryan Williams 2010 erzielte vielleicht bahnbrechendste Resultat der Komplexitätstheorie der letzten vier Jahrzehnte betrifft Schranken der Berechnungskraft von sog. ACC-Schaltkreisfamilien, Schaltkreisfamilien konstanter Tiefe, die neben den üblichen Gattern für Konjunktion, Disjunktion und Negation auch Gatter für Modulo-Tests verwenden dürfen. Das Resultat soll nachvollzogen werden. Der Beweis beruht auf einem sehr überraschenden Zusammenhang, in dem eine obere Schranke zu einer unteren Schranke führt: Williams zeigt, dass für viele Schaltkreisklassen schnellere Satisfiability-Algorithmen zu unteren Schranken führen.

Literatur:

• Ryan Williams, Improving exhaustive search implies superpolynomial lower bounds, https://doi.org/10.1137/10080703X, 2013.
• Ryan Williams, Nonuniform ACC Circuit Lower Bounds, https://doi.org/10.1145/2559903, 2014.

Von vielen wichtigen Komplexitätsklassen ist bekannt, dass sie aus sehr einfachen Funktionen (Nachfolger, Identität, etc.) mit Hilfe verschiedener Rekursionsschema generiert werden können. Einzelresultate dieses Gebietes sollen dargestellt werden.

Die Korrektheit von Aussagen ist in der Kryptographie ein wichtiger Aspekt. Neben den offensichtlichen sicherheitskritischen Anwendungen, die ein hohes Maß an Sicherheit erfordern, führen Fehler im kryptographischen System selten zufällig zu Problemen, sondern werden von Angreifern gezielt herbeigeführt. Dies erschwert die Erstellung geeigneter Protokolle zusätzlich, da diese nicht nur für den Verwendungszweck des Systems, sondern für alle denkbaren Angriffsszenarien ausgelegt sein müssen. Dabei muss sichergestellt werden, dass durch die Kombination bestimmter (sicherer) Primitive keine Schwächen in das resultierende System eingebaut werden.
Die Abschlussarbeit soll sich mit aktuellen Entwicklungen in diesem Themengebiet auseinandersetzen und den Stand der Forschung darstellen. 

Literatur:

• Russell Impagliazzo und Bruce M. Kapron. ”Logics for reasoning about cryptographic constructions“. In: Journal of Computer and System Sciences 72.2 (2006). JCSS FOCS 2003 Special Issue, S. 286–320. issn: 0022-0000. doi: https://doi.org/10.1016/j.jcss.2005.06.008

Background and Motivation: Conventional machine learning systems, particularly those relying on "Big Data", demand massive training resources, suffer from high training costs, and often lack generalization capabilities in unknown environments. In contrast, human cognition often relies on "intuition"—spontaneous, experience-based decisions made without explicitly calculating statistical probabilities.

Recent theoretical frameworks propose that the mathematical concepts of sheaves and cohomology groups represent this holistic information processing. Sheaves map local data inputs to globally consistent structures. Through coherence conditions, local information fragments are seamlessly merged into a global "Gestalt". Sir Roger Penrose prominently utilized the first cohomology group, $H^1$, to demonstrate how impossible figures (like the Penrose triangle) make sense locally but contain mathematical obstructions preventing a global existence.

This project aims to translate these highly abstract mathematical concepts into an algorithmic model for simulated intuition. By interpreting local visual inputs (e.g., edges, textures) as sections of a sheaf, visual perception can be modeled as the immediate mathematical derivation of a global section.

Project Objectives and Tasks: The core objective of this thesis is to create a functional demo version that applies sheaf cohomology to visual pattern recognition, specifically focusing on the perception of fragmented images.

Your tasks will include:

• Mathematical Modeling: Defining a covering topology for visual domains, such as overlapping image patches.  
• Sheaf Construction: Defining a specific sheaf where local features are mapped to vectors, and establishing restriction mappings (projections) for their overlaps.
• Demo Creation: Building a "Fragmented Images" experiment to test the algorithm, in analogy to Penrose’s demonstration.

Literatur:

• Penrose, Roger (1991): On the Cohomology of Impossible Figures. In: Structural Topology, Nr. 17, S. 11–16.
• Mac Lane, Saunders/Moerdijk, Ieke (1992): Sheaves in Geometry and Logic: A First Introduction to Topos Theory. New York: Springer (Universitext)

Für die Bachelorarbeit soll eine umfassende Wissens- und Literaturdatenbank zu Dependence Logic, basierend auf den theoretischen Grundlagen von Jouko Väänänen, unter Nutzung der Plattform Open Research Knowledge Graph (ORKG) erstellt werden. Die Arbeit umfasst zunächst eine gründliche Analyse des aktuellen Forschungsstandes zu Dependence Logic sowie das Sammeln und systematische Erfassen relevanter wissenschaftlicher Publikationen wie Artikel, Bücher und Konferenzbeiträge. Anschließend wird das Wissen in strukturierter Form modelliert, indem zentrale Begriffe, Theorien und Methoden aus dem Bereich der Dependence Logic in sogenannte Contribution-Templates und passende Entitäten und Relationen innerhalb des ORKG eingebettet werden. Das Ziel ist es, diese modellierte Wissensbasis auf ORKG nach den FAIR-Prinzipien (Findable, Accessible, Interoperable, Reusable) zugänglich zu machen, sodass sie sowohl von Forschenden als auch maschinell genutzt werden kann. Dabei werden auch passende Such-, Vergleichs- und Visualisierungsfunktionen der ORKG-Werkzeuge integriert, um die wissenschaftlichen Inhalte transparent und nachvollziehbar aufzubereiten und zugänglich zu machen. Die Arbeit schließt mit der Dokumentation der methodischen Vorgehensweise zur Wissensakquise, Modellierung und Integration in das ORKG sowie einer kritischen Reflexion über die Möglichkeiten, Herausforderungen und den Mehrwert einer solchen Wissensdatenbank im wissenschaftlichen Umfeld.

Die Betreuung wird zweigeteilt sein (Dependence Logik THI, ORKG TIB).

Literatur:

• Jouko A. Väänänen: Dependence Logic - A New Approach to Independence Friendly Logic. London Mathematical Society student texts 70, Cambridge University Press 2007, ISBN 978-0-521-70015-3, pp. I-IX, 1-225

Theoretische Untersuchungen der Berechnungskraft (optimal trainierter) neuronaler Netze, der Komplexität des Lernprozesses, der Beziehung zu diversen logischen Kalkülen wurden in den letzten Jahren veröffentlicht. Ergebnisse aus diesem sehr aktuellen Forschungsbereich sollen vorgestellt und zusammengefasst werden. Es sind verschiedene Bachelor- und Master-Arbeiten möglich!

Literatur:

• Gustav Šír, From Graph ML to Deep Relational Learning, https://towardsdatascience.com/from-graph-ml-to-deep-relational-learning-f07a0dddda89.
• Michael Benedikt et al, Decidability of Graph Neural Networks via Logical Characterizations, 2024. https://doi.org/10.4230/LIPIcs.ICALP.2024.127
• Lena Strobl et al, What Formal Languages Can Transformers Express? A Survey, 2024, https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00663/120983/What-Formal-Languages-Can-Transformers-Express-A
• Adrian Wurm, Complexity of Reachability Problems in Neural Networks, 2024. https://www.springerprofessional.de/complexity-of-reachability-problems-in-neural-networks/26128096

In der Quantenmechanik werden nicht erklärbare oder zufällige Phänomene teilweise auf das Vorhandensein sog. verborgener Variablen oder Parameter zurückgeführt. Die sog. Teamlogik erlaubt eine rein logische Beschreibung und Analyse dieser Phänomene. Ein Überblick über das Gebiet soll gegeben werden.

Literatur:

• Rafael Albert und Erich Grädel, Unifying Hidden-Variable Problems from Quantum Mechanics by Logics of Dependence and Independence, www.sciencedirect.com/science/article/pii/S0168007222000021, 2022.