Technische Universität Ilmenau, Bachelorarbeit 2023
Lovász erkannte als einer der ersten den engen Zusammenhang zwischen der Anzahl der Subgraphen #Sub(H, G) und der Anzahl der Homomorphismen #Hom(H, G). Radu Curticapean, Holger Dell und Dániel Marx formalisierten diese Erkenntnisse unter dem Namen der ‚Graph Motif Parameter‘. Des Weit- eren zeigten sie, dass #Sub(H, G) = ∑ ρ (−1)|V (H)|−|V (Hρ )| &hahog; ∏ B∈ρ(|B| − 1)! #Aut(H) &hahog; #Hom(Hρ, G) (1) gilt [?]. In dieser Arbeit analysieren wir das Zählen von Pfaden mittels graphHom2. Wir zeigen, dass es unter gewissen Annahmen keinen Algorithmus der Laufzeit f (k)&hahog;no(&worte;k/ log(&worte;k)) für das Zählen von k-Pfaden in einem Zielgraph auf n-Ecken gibt, sofern wir graphHom2 nutzen, wobei f eine berechenbare Funktion ist die nur von k abhängt. Außerdem beweisen wir, dass Pfade, unter allen zusammenhängenden Graphen, die Anzahl der zu betrachtenden Quotientengraphen Qρ maximieren. Zudem befassen wir uns mit dem Entscheidungsproblem, Pfade in Graphen aufzufinden, und zeigen eine hinreichende Existenzbedingung für Pk ⊆ G.
Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps. - In: Journal of the ACM, ISSN 1557-735X, Bd. 70 (2023), 5, 32, S. 32:1-32:32
We prove near-optimal tradeoffs for quantifier depth (also called quantifier rank) versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least nΩ (k/log k). Our tradeoffs also apply to first-order counting logic and, by the known connection to the k-dimensional Weisfeiler-Leman algorithm, imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique introduced by Razborov in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the minimal quantifier depth needed to distinguish them in finite variable logics.
https://doi.org/10.1145/3195257
A dichotomy for succinct representations of homomorphisms. - In: 50th International Colloquium on Automata, Languages, and Programming, (2023), S. 113:1-113:19
The task of computing homomorphisms between two finite relational structures A and B is a well-studied question with numerous applications. Since the set Hom(A, B) of all homomorphisms may be very large having a method of representing it in a succinct way, especially one which enables us to perform efficient enumeration and counting, could be extremely useful. One simple yet powerful way of doing so is to decompose Hom(A, B) using union and Cartesian product. Such data structures, called d-representations, have been introduced by Olteanu and Závodný [Olteanu and Závodný, 2015] in the context of database theory. Their results also imply that if the treewidth of the left-hand side structure A is bounded, then a d-representation of polynomial size can be found in polynomial time. We show that for structures of bounded arity this is optimal: if the treewidth is unbounded then there are instances where the size of any d-representation is superpolynomial. Along the way we develop tools for proving lower bounds on the size of d-representations, in particular we define a notion of reduction suitable for this context and prove an almost tight lower bound on the size of d-representations of all k-cliques in a graph.
https://doi.org/10.4230/LIPIcs.ICALP.2023.113
Answering (unions of) conjunctive queries using random access and random-order enumeration. - In: ACM transactions on database systems, ISSN 0362-5915, Bd. 47 (2022), 3, S. 9:1-9:49
As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tractability yardstick of answer enumeration with a polylogarithmic delay after a linear-time preprocessing phase. Such an evaluation is obtained by constructing, in the preprocessing phase, a data structure that supports polylogarithmic-delay enumeration. In this article, we seek a structure that supports the more demanding task of a “random permutation”: polylogarithmic-delay enumeration in truly random order. Enumeration of this kind is required if downstream applications assume that the intermediate results are representative of the whole result set in a statistically meaningful manner. An even more demanding task is that of “random access”: polylogarithmic-time retrieval of an answer whose position is given. We establish that the free-connex acyclic CQs are tractable in all three senses: enumeration, random-order enumeration, and random access; and in the absence of self-joins, it follows from past results that every other CQ is intractable by each of the three (under some fine-grained complexity assumptions). However, the three yardsticks are separated in the case of a union of CQs (UCQ): while a union of free-connex acyclic CQs has a tractable enumeration, it may (provably) admit no random access. We identify a fragment of such UCQs where we can guarantee random access with polylogarithmic access time (and linear-time preprocessing) and a more general fragment where we can guarantee tractable random permutation. For general unions of free-connex acyclic CQs, we devise two algorithms with relaxed guarantees: one has logarithmic delay in expectation, and the other provides a permutation that is almost uniformly distributed. Finally, we present an implementation and an empirical study that show a considerable practical superiority of our random-order enumeration approach over state-of-the-art alternatives.
https://doi.org/10.1145/3531055
Über praktisch schnelle Verfahren zur Konstruktion von Suffixarrays. - Ilmenau. - 145 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022
Suffixarrays sind eine der zentralen Datenstrukturen für String-Algorithmen und finden weitreichende praktische Anwendungen. Die effiziente Konstruktion dieser ist seit der ersten Veröffentlichung in 1990 ein sehr reges Forschungsgebiet geblieben. Im Jahr 2006 wurde der Algorithmus DivSufSort veröffentlicht und obwohl seitdem eine Vielzahl weiterer Suffixarray-Konstruktions-Algorithmen entwickelt wurden, konnte dieser in seiner praktischen Performanz 15 Jahre lang nicht unterboten werden. Doch im Jahr 2021 wurde ein neuer Algorithmus GSACA-DS vorgestellt, welcher unter Verwendung von speziellen Eigenschaften von Lyndon-Wörtern DivSufSort endlich in der Praxis schlagen kann. Obwohl DivSufSort solch hohe praktische Relevanz hat, entzog sich dieser bisher einer rein formellen Darstellung. GSACA-DS besitzt einen formal komplexen Ansatz, weshalb die originale Arbeit keine vollständige Grundlage für dessen Funktionsweise darstellt. Im Rahmen dieser Arbeit sollen diese Lücken in der Literatur gefüllt werden, indem beide Verfahren inklusive ihrer theoretischen Grundlagen vorgestellt, analysiert und zum ersten Mal deren Korrektheit bewiesen werden.
Peeling close to the orientability threshold - spatial coupling in hashing-based data structures. - In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, (2021), S. 2194-2211
https://dl.acm.org/doi/10.5555/3458064.3458195
Fairness in personnel scheduling. - Ilmenau. - 88 Seiten
Technische Universität Ilmenau, Masterarbeit 2021
Die Personaleinsatzplanung ist ein komplexes Optimierungsproblem, bei dem es um die Zuteilung von Mitarbeitern zum Arbeitsplan in einer Vielzahl von Branchen geht. In dieser Arbeit betrachten wir eine spezielle Variante, die "faire" Einsatzpläne erstellen soll. Der Arbeitgeber hat, ähnlich wie bei der traditionellen Personaleinsatzplanung, die Kontrolle über die Zuweisung von Einsatzorten und Arbeitszeiten an die Arbeitnehmer. Andererseits steht es den Arbeitnehmern frei, Präferenzen für die von ihnen gewünschte Arbeit zu äußern. Durch diese Präferenzen werden die Mitarbeiter in das Planungssystem einbezogen, was sich positiv auf die Arbeitsmoral und die Produktivität auswirken soll. Ziel ist es, ein faires Planungssystem zu schaffen, das den Anforderungen des Unternehmens gerecht wird und die Arbeitswünsche der Mitarbeiter berücksichtigt. In dem in dieser Arbeit vorgeschlagenen Modell geben die Unternehmen ihren Bedarf für jeden Tag an, und die Arbeitnehmer geben ihre Präferenzen an. Unser Algorithmus versucht, einen Plan zu erstellen, der sowohl für Arbeitgeber als auch für Arbeitnehmer eine Win-Win-Situation darstellt. Um dies zu erreichen, versuchen wir, einen Zeitplan zu erstellen, der den Anforderungen des Unternehmens und den Präferenzen der Arbeitnehmer so weit wie möglich gerecht wird. Wir haben den Algorithmus mit drei verschiedenen Ansätzen implementiert. Mit allen drei Ansätzen wurden verschiedene Computerexperimente durchgeführt, und ihre Ergebnisse werden diskutiert. Unser Ansatz erstellt erfolgreich einen kurz-, mittel- und langfristigen Zeitplan, der zu einem guten Prozentsatz die Präferenzen der Mitarbeiter erfüllt.
Analyse und experimentelle Evaluation moderner Heap-Strukturen. - Ilmenau. - 98 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021
Diese Arbeit befasst sich mit einer seit 2015 existierenden Idee für die Implementierung von Prioritätswarteschlangen. Es handelt sich dabei um die von Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan und Uri Zwick vorgeschlagenen "Hollow Heaps". Von den klassischen Fibonacci-Heaps unterscheiden sie sich dadurch, dass sie auf die Cascading-Cut-Prozedur verzichten und stattdessen ein Konzept "leerer Knoten" einführen und teils sogar auf die für Heaps übliche Baumstruktur verzichten. Diese Arbeit stellt Fibonacci-Heaps und Hollow Heaps einheitlich und ausführlich dar und führt experimentelle Vergleiche. In dieser Arbeit wird gezeigt, dass die Wahl zwischen Fibonacci-Heaps und Hollow Heaps bis auf in wenigen Ausnahmen zugunsten der Hollow Heaps ausfallen sollte. Weiterhin sind in unseren Experimenten Binärheaps - als wahrscheinlich grundlegendste Heapstruktur - sogar schneller als ihre Konkurrenten.
Foundations for actively secure card-based cryptography. - In: 10th International Conference on Fun with Algorithms, (2020), S. 17.1-17:23
https://doi.org/10.4230/LIPIcs.FUN.2021.17
Random hypergraphs for hashing-based data structures. - Ilmenau : Universitätsbibliothek, 2020. - 1 Online-Ressource (ix, 165 Seiten)
Technische Universität Ilmenau, Dissertation 2020
Diese Arbeit behandelt Wörterbücher und verwandte Datenstrukturen, die darauf aufbauen, mehrere zufällige Möglichkeiten zur Speicherung jedes Schlüssels vorzusehen. Man stelle sich vor, Information über eine Menge S von m = |S| Schlüsseln soll in n Speicherplätzen abgelegt werden, die durch [n] = {1, ,n} indiziert sind. Jeder Schlüssel x [ELEMENT OF] S bekommt eine kleine Menge e(x) [SUBSET OF OR EQUAL TO] [n] von Speicherplätzen durch eine zufällige Hashfunktion unabhängig von anderen Schlüsseln zugewiesen. Die Information über x darf nun ausschließlich in den Plätzen aus e(x) untergebracht werden. Es kann hierbei passieren, dass zu viele Schlüssel um dieselben Speicherplätze konkurrieren, insbesondere bei hoher Auslastung c = m/n. Eine erfolgreiche Speicherung der Gesamtinformation ist dann eventuell unmöglich. Für die meisten Verteilungen von e(x) lässt sich Erfolg oder Misserfolg allerdings sehr zuverlässig vorhersagen, da für Auslastung c unterhalb eines gewissen Auslastungsschwellwertes c* die Erfolgswahrscheinlichkeit nahezu 1 ist und für c jenseits dieses Auslastungsschwellwertes nahezu 0 ist. Hauptsächlich werden wir zwei Arten von Datenstrukturen betrachten: - Eine Kuckucks-Hashtabelle ist eine Wörterbuchdatenstruktur, bei der jeder Schlüssel x [ELEMENT OF] S zusammen mit einem assoziierten Wert f(x) in einem der Speicherplätze mit Index aus e(x) gespeichert wird. Die Verteilung von e(x) wird hierbei vom Hashing-Schema festgelegt. Wir analysieren drei bekannte Hashing-Schemata und bestimmen erstmals deren exakte Auslastungsschwellwerte im obigen Sinne. Die Schemata sind unausgerichtete Blöcke, Doppel-Hashing sowie ein Schema für dynamisch wachsenden Schlüsselmengen. - Auch eine Retrieval-Datenstruktur speichert einen Wert f(x) für alle x [ELEMENT OF] S. Diesmal sollen die Werte in den Speicherplätzen aus e(x) eine lineare Gleichung erfüllen, die den Wert f(x) charakterisiert. Die entstehende Datenstruktur ist extrem platzsparend, aber ungewöhnlich: Sie ist ungeeignet um Fragen der Form "ist y [ELEMENT OF] S?" zu beantworten. Bei Anfrage eines Schlüssels y wird ein Ergebnis z zurückgegeben. Falls y [ELEMENT OF] S ist, so ist z = f(y) garantiert, andernfalls darf z ein beliebiger Wert sein. - Wir betrachten zwei neue Hashing-Schemata, bei denen die Elemente von e(x) in einem oder in zwei zusammenhängenden Blöcken liegen. So werden gute Zugriffszeiten auf Word-RAMs und eine hohe Cache-Effizienz erzielt. Eine wichtige Frage ist, ob Datenstrukturen obiger Art in Linearzeit konstruiert werden können. Die Erfolgswahrscheinlichkeit eines naheliegenden Greedy-Algorithmus weist abermals ein Schwellwertverhalten in Bezug auf die Auslastung c auf. Wir identifizieren ein Hashing-Schema, das diesbezüglich einen besonders hohen Schwellwert mit sich bringt. In der mathematischen Modellierung werden die Speicherpositionen [n] als Knoten und die Mengen e(x) für x [ELEMENT OF] S als Hyperkanten aufgefasst. Drei Eigenschaften der entstehenden Hypergraphen stellen sich dann als zentral heraus: Schälbarkeit, Lösbarkeit und Orientierbarkeit. Weite Teile dieser Arbeit beschäftigen sich daher mit den Wahrscheinlichkeiten für das Vorliegen dieser Eigenschaften abhängig von Hashing Schema und Auslastung, sowie mit entsprechenden Schwellwerten. Eine Rückübersetzung der Ergebnisse liefert dann Datenstrukturen mit geringen Anfragezeiten, hoher Speichereffizienz und geringen Konstruktionszeiten. Die theoretischen Überlegungen werden dabei durch experimentelle Ergebnisse ergänzt und gestützt.
https://www.db-thueringen.de/receive/dbt_mods_00047127