Termine Vorträge (Archiv)

Treffer 51 - 100 von 152 Ergebnissen

  • Termin
     
    Titel
  • 28.09.2018
    10:15 - 11:00
    BSc
    Algorithms for the Maximum Common Subtree Isomorphism Problem
    Florian Frantzen
    The maximum common subtree isomorphism problem asks for the largest possible isomorphism among all common subtree isomorphisms between two unrooted input trees. This can either be formulated in terms of the size of the common subtree, or more generally with respect to a weight function. Its more general formulation of a maximum common subgraph isomorphism problem, which permits arbitrary input graphs instead of only trees, is known to be NP-complete. The restricted setting allows for efficient polynomial time algorithms. We present a particular recent algorithm due to Droschinsky, Kriege and Mutzel for this problem. For unrooted trees of order n and degree Delta, this algorithm achieves a worst-case running time of O(n^2 Delta). We complement this theoretical description of the algorithm with various tests of possible changes to the algorithm and compare their impacts on our own implementation of the algorithm. We also compare our implementation to other programs that can be used to compute a solution for the maximum common subtree isomorphism problem.
  • 28.09.2018
    11:00 - 11:45
    BSc
    The quantifier depth for distinguishing structures in first-order logic
    Bianka Bakullari
    The Weisfeiler-Leman algorithm is a combinatorial procedure used to distinguish non-isomorphic graphs. I give an introduction to the mechanisms of the algorithm by putting the focus on the 2-dimensional variant of it, for which I explain the non-trivial upper bound O(n^2/log n) on the number of iterations. Then graphs are defined as relational structures to show the connection between the dimension of the algorithm and the number of variables used in logics with counting. In the end, we show an approach to represent arbitrary finite relational structures as colored graphs in a way that we can apply the Weisfeiler-Leman algorithm to distinguish them. We use the connection between the algorithm and logics with counting to make claims about the quantifier depth of the formulas that distinguish non-isomorphic finite relational structures.
  • 28.09.2018
    11:45 - 12:30
    BSc
    Parameterized Approximability of Dominating Set
    Daniel Schleiz
    Due to the NP-hardness of the Dominating Set decision problem, there is no efficient algorithm solving it unless P=NP. Seperate approximation and parameterization approaches to make this problem more tractable have shown to yield dissatisfactory results. Thus the parameterized approximability of Dominating Set has been an open question for a while, where for a Graph G with n vertices and an integer k given as input, an algorithm computing a dominating set of size at most H(k)*k with a runtime of F(k)*poly(n) for some computable functions H,F is of interest. Only recently Karthik, Laekhanukit and Manurangsi (2018) were able to rule out such an algorithm under the assumption of W[1]!=FPT. In this bachelor thesis talk, the proof for this result will be presented along with the needed background on parameterized complexity. Furthermore, a stronger runtime lower bound of F(k)*n^{o(k)} up to the same approximation ratio assuming the Exponential Time Hypothesis will be shown, resulting from the same work of Karthik et al.
  • 28.09.2018
    12:30 - 13:15
    BSc
    Optimization-based Hierarchical Clustering
    Michael Scholkemper
    Hierarchical clustering is a data analysis method that recursively partitions a given data set into increasingly smaller clusters. The structure that is obtained from this procedure is then represented by a tree - or a dendogram. This thesis presents the work by [Dasgupta, 2016] and the subsequent work by [Cohen-Addad et al., 2018] that spawned the theoretical study of the problem. Therein an optimization framework for Hierarchical Clustering is established by defining an objective function, thus framing it as a combinatorial optimization problem. This thesis presents the needed theory for the proposed optimization framework and provides approximation algorithms for both similarity and dissimilarity inputs as. Additionally, a family of inputs constrained in such a way as to admit efficient Hierarchical Clustering is presented.
  • 27.09.2018
    14:00 - 14:45
    MSc
    Optimization for the complementation of Büchi automata
    Lasse Nitz
  • 26.09.2018
    11:00 - 12:00
    MSc
    Real-valued Connectivity Systems
    Eva Fluck
    Based on a survey on connectivity, decompositions and tangles by Grohe [5], we adapt the so far integer-valued theory onto real-valued set functions. We start by adapting the definition of finite connectivity systems including the def- inition of connectivity functions and give examples of different functions and uni- verses. A connectivity function is a set function κ : 2 U → R on a finite universe U , which is symmetric, normalized and submodular, that is, for all X, Y ∈ U , κ(X)+κ(Y ) ≥ κ(X ∩Y )+κ(X ∪Y ). We find that the codomain of κ is discrete. This allows us, similar to integer-values, to do inductive arguments using a value called granularity, which is the smallest non-zero difference between two function values. Then we look at the definitions of tangles, which we view as highly connected regions of the universe, and branch decompositions, which are tree like decompositions of the universe related to the well-known tree decompositions, into this new setting. We are able to prove that both definitions behave similar to integer-valued systems. Next we derive the duality theory between branch decompositions and tangles, first developed by Robertson and Seymour [11]. This duality states, that we can construct a branch decomposition of a certain width k if there is no tangle of order k and that a branch decomposition of width k is a witness for the non-existence of a tangle of order k. So far this duality was mostly based on the submodularity of the set function. We find additional functions, where branch decomposition is also dual to tangles. We find a property of the set function that we call submodular bounded, that is, for all sets X, Y ∈ U and all k ∈ R, if κ(X), κ(Y ) ≤ k then κ(X ∩ Y ), κ(X ∪ Y ) ≤ k. Submodular bounded leads to an equivalent duality theory as submodularity. Lastly, we show that there is a way to canonically decompose real-valued connectivity systems into their maximal tangles.
  • 26.09.2018
    12:00 - 12:45
    BSc
    Distance-Aware Colour Refinement
    Björn Plewinski
    Color refinement is a graph algorithm used in isomorphism testing which also shows great promise in designing graph kernels for machine learning applications. This bachelor thesis explores an extension of this algorithm which incorporates distances between vertices. We will examine the algorithms theoretical properties and compare it and its performance with the standard color refinement algorithm and the two-dimensional Weisfeiler-Leman algorithm.
  • 25.09.2018
    10:00 - 10:30
    BSc
    Nondeterministic automata with deterministic acceptance strategies
    Domenic Quirl
  • 25.09.2018
    10:45 - 11:15
    BSc
    Canonical automata for regular languages
    Magnus Groß
  • 14.09.2018
    11:00 - 12:00
    MSc
    Structural Similarity and Homomorphism Counts
    Jan Böker
    Recent results show how the structural similarity of graphs can be characterized by counting homomorphisms to them. We show how homomorphism counts characterize the structural similarity of related relational structures, with a focus on directed graphs, (vertex-)colored graphs, and multi-hypergraphs. We prove that two directed graphs G and H are isomorphic if and only if, for every directed acyclic graph D, the number of homomorphisms Hom(D,G) from D to G is equal to the corresponding number Hom(D,H) from D to H. Our approach also yields a similar statement for undirected graphs, where it suffices to count homomorphisms from three-colorable graphs. We show how, after encoding a colored graph as an uncolored one, counts of homomorphisms to these graphs can be obtained from each other. This allows us to generalize a recent result on uncolored graphs, obtaining that two colored graphs G and H are not distinguished by the color-refinement algorithm if and only if, for every colored tree T, we have Hom(T, G) = Hom(T, H). Additionally, this reduction also works for a generalization of said result to bounded treewidth. We introduce a generalization of the color-refinement algorithm for multi-hypergraphs and prove that it does not distinguish two multi-hypergraphs G and H if and only if, for every Berge-acyclic multi-hypergraph B, we have Hom(B, G) = Hom(B, H). To this end, we show how homomorphisms of multi-hypergraphs and their colored incidence graphs are related to each other.
  • 14.09.2018
    12:00 - 12:45
    BSc
    End-to-End Graph Learning
    Emre Yamen
    In der Präsentation wird End-to-End Graph Learning definiert, was eine Möglichkeit der Graphen Klassifizierung ist. Zudem wird erklärt wie man Graphen kanonisieren kann. Danach wird eine aktuelle Methode zur Graphen Klassifizierung präsentiert, die Graph Kernel. Da wird mehr auf die Weisfeiler-Leman subtree kernel eingegangen. Danach werden Experimente zur Graphen Klassifizerung mit End-to-End Graph Learning und Graph Kanonisierung in einem neuronalen Netzwerk vorgestellt. Das Ergebnis wird mit dem Ergebnis vom Weisfeiler-Leman subtree kernel in Neuronalen Netzwerken verglichen.
  • 05.09.2018
    09:30 - 10:30
    BSc
    Similarity of Small Graphs
    Stefanie Winkler
    The graph similarity problem deals with the computation of the distance between two given graphs and is therefore closely related to graph isomorphism. There are different approaches to define this distance. This thesis mainly deals with the Frobenius distance. Besides proving the NP-completeness of the problem, we examine its behavior on small graphs. To achieve this, we implement it as a mathematical optimization model in Java using the tool CPLEX. We use the implementation to compute the distance of all graphs up to size five and for some selected bigger graphs. To summarize the results, we present them in multiple plots showing the occurring distances and the runtime. Since the problem is NP-hard, it is not efficient to solve unless P = NP. Therefore, we approximate the exact calculation by convex relaxation. We examine the resulting measure as done for the unrelaxed case. Furthermore, we directly compare the computed distances on pairs of graphs to analyze the ratio between the two. Other approaches to graph similarity include the minimum graph edit distance and the maximum common subgraph. We present their respective definition and prove their NP-hardness.
  • 29.08.2018
    10:00 - 11:00
    BSc
    Graph Autoencoder
    Florian Behrens
  • 29.08.2018
    10:00 - 11:00
    BSc
    Graph Autoencoder
    Florian Behrens
  • 24.08.2018
    10:00 - 10:30
     
    Climbing up the elementary complexity classes with theories of automatic structures
    Peter Lindner
    Automatic structures are of particular interest, since their first order theories are decidable. While these theories might be of non-elementary complexity in general, the practically relevant examples are located below 3-fold exponential time (e. g. Presburger arithmetic and automatic structures of bounded degree). It was an open question [Durand-Gasselin], whether there are automatic structures with theories of higher elementary complexity. In my masters thesis, I introduced a family of automatic structures, roughly covering all of the complexity classes k-EXPTIME for k > 2. Presented in this talk is now the joint work with Faried Abu Zaid and Dietrich Kuske (TU Ilmenau), who were able to close the remaining gaps and thus give an exact characterization of the complexity of the mentioned structures. The presented proofs contain various involved encoding techniques.
  • 16.08.2018
    15:00 - 16:00
    MSc
    Titel: Colour Refinement and Fractional Isomorphism on Weighted Structures
    Hinrikus Wolf
    Colour refinement is a basic algorithm for graph isomorphism testing. It splits the vertex set of a graph until all vertices in a class have the same number of neighbours in every other class. The resulting partition is called (coarsest) equitable partitionof a graph. Tinhofer, Ramana et al. and Godsil found a tight connection between equitable partitions of a graph and fractional automorphisms, which are the LP relaxation of the natural ILP formulation of graph isomorphism. Grohe et al. generalised the colour refinement algorithm for weighted bipartite graphs in a matrix representation and they introduced a theory of equitable partitions, fractional automorphisms and fractional isomorphisms for weighted bipartite graphs in a matrix representation. We develop a series of generalisations and extensions of their theory. Firstly, we modify the colour refinement algorithm to work on weighted directed graphs in matrix representation. Furthermore, we extend the theory of equitable partitions, fractional automorphisms and fractional isomorphisms to weighted directed graphs. Secondly, we adapt the results for graphs with an additional weighted unary or binary relation. Then we adapt Atserias’ and Maneva’s definition of k-equitable partitions to state the k-dimensional colour refinement algorithm for weighted directed graphs. Thirdly, we generalise k-equitable partitions and k-dimensional colour refinement to weighted τ-structures. In the end, we state a general theorem on the consistent theory of equitable partitions, fractional automorphisms and fractional isomorphisms.
  • 15.06.2018
    10:15 - 11:15
     
    A unified approach to Büchi determinisation
    Anton Pirogov
    Nondeterministic Büchi automata are one of the simplest types of finite automata on infinite words and are successfully applied in model checking. In some settings nondeterminism is not feasible in practice, but determinisation of Büchi automata is a difficult problem with a long history and a few different solutions. In our work we noticed similarities in two different determinisation constructions and studied those to obtain a generalized algorithm from which both original constructions can be recovered as special cases. In this talk I will sketch both constructions, illuminate their relationship and give an idea of the unified procedure. (Joint work with Christof Löding)
  • 25.05.2018
    10:15 - 11:15
     
    Obstacles for better algorithms for the Graph Isomorphism Problem
    Daniel Neuen
    I will mainly talk about a new algorithm solving the isomorphism problem for graphs of maximum degree d in time n^{polylog(d)} where n denotes the number of vertices of the input graphs. The previous best algorithm for this problem due to Luks runs in time n^{O(d)}. This result also improves on the recent quasipolynomial time algorithm for the general graph isomorphism problem due to Babai and in particular results in a faster algorithm for graphs of logarithmic degree, one of the bottleneck cases in Babai's algorithm. If time permits I will also discuss further bottleneck cases for Babai's algorithm and present some open questions regarding these cases.
  • 18.05.2018
    10:15 - 11:15
     
    Tree Automata with Global Constraints
    Patrick Landwehr
    We study an extension of standard tree automata that allows for testing (dis)equality of subtrees, which may be arbitrary far away from each other. We introduce a general model, look at known results on finite trees and discuss where these results can be extended to infinite trees. In particular, we briefly tackle closure properties and then analyze the decidability of the universality- and emptiness-problem.
  • 04.05.2018
    10:15 - 11:15
     
    Lovasz meets Weisfeiler and Leman
    Martin Grohe
    I will speak about an unexpected correspondence between a beautiful theory, due to Lovasz, about homomorphisms and graph limits and a popular heuristic for the graph isomorphism problem known as the Weisfeiler-Leman algorithm. I will also relate this to graph kernels in machine learning. Indeed, the context of this work is to desgin and understand similarity measures between graphs and discrete structures. (Joint work with Holger Dell and Gaurav Rattan.)
  • 04.05.2018
    10:15 - 11:15
     
    Lovasz meets Weisfeiler and Leman
    Martin Grohe
    I will speak about an unexpected correspondence between a beautiful theory, due to Lovasz, about homomorphisms and graph limits and a popular heuristic for the graph isomorphism problem known as the Weisfeiler-Leman algorithm. I will also relate this to graph kernels in machine learning. Indeed, the context of this work is to desgin and understand similarity measures between graphs and discrete structures. (Joint work with Holger Dell and Gaurav Rattan.)
  • 19.04.2018
    10:30 - 11:30
     
    Algorithmic Approaches to Testing Isomorphism of Graphs of Bounded Treewidth
    Lisa Mannel
    The graph isomorphism problem is the problem of deciding for two given graphs whether there exists a bijection between their vertices that preserves the edge relation. It is one of the classical problems in NP for which we do not know whether it is in P. However, many results have been found on the complexity of certain graph classes, for example for graphs of bounded treewidth. We develop a new algorithm which decides isomorphism for two graphs given together with their isomorphism-invariant nested tree decompositions. It employs a subroutine GIT (short for Graph Isomorphism Test), which can be any algorithm deciding isomorphism for colored graphs. The running time of our algorithm heavily depends on the running time of GIT and the properties of the given isomorphism-invariant nested tree decompositions. Our second contribution is the collection and combination of existing algorithms to compute an algorithm that outputs an isomorphism-invariant nested tree decomposition of a given graph. The combination of this algorithm with our approach to testing isomorphism introduced above, which employs Babai's quasi-polynomialtime algorithm as the subroutine GIT, allows us to decide isomorphism for graphs of treewidth bounded by k in time 2^{O((k^2 log k)^c)}*p(n), for some polynomial p and a constant c.
  • 26.01.2018
    10:15 - 11:15
    ATI
    SMT-based Flat Model- Checking for LTL with Counting
    Anton Pirogov
  • 23.01.2018
    10:00 - 11:00
     
    Provenance for Logics with Team Semantics
    Lukas Huwald
    Master Kolloquium Abstract: Provenance analysis is a concept that originated in the field of database theory which unifies several nonstandard semantics for database queries, such as bag semantics or probabilistic semantics. These different semantics can be captured in an algebraic framework using various semirings, and are special instances of computations in a general provenance semiring. While the previous work on provenance semantics focused mainly on positive query languages for databases, Grädel and Tannen recently introduced provenance semantics for logical languages that also include negation, e.g. full first order logic. In this master thesis talk we introduce semiring semantics and provenance analysis for logics with team semantics, such as Väänänen's dependence logic. The main features of these logics are atomic formulae that allow reasoning about dependence and independence relations between variables. We define semiring semantics for these logics and analyze their properties, e.g. with respect to locality, closure properties and game theoretic semantics. We show that in the class of idempotent semirings, many of the known results for booolean semantics are preserved when considering semiring semantics. This is not the case for general semirings: many logics that are equivalent for boolean semantics can be separated for semiring semantics. In particular we show that independence logic and existential second order logic are incomparable for semiring semantics, but certain extensions of these logics remain equivalent.
  • 19.01.2018
    10:15 - 11:15
    ATI
    Theories of Automatic Structures within the Exponential Time Hierarchy
    Peter Lindner
  • 22.12.2017
    10:15 - 11:15
    ATI
    Capacity of Neural Net- works for Lifelong Learn- ing of Composable Tasks
    work by Leslie G. Valiant
    Speaker: Dominik Meier
  • 18.12.2017
    10:00 - 10:30
     
    Learning Algorithms for Sequential Transducers
    Tom Biskup
    Bachelor talk
  • 15.12.2017
    10:15 - 11:15
    ATI
    Learning Symbolic Automata
    work by Samuel Drews and Loris D'Antoni
    Speaker: Leo Krömker
  • 08.12.2017
    10:15 - 11:15
    ATI
    Set Similarity Search Beyond MinHash
    work by Tobias Christiani, Rasmus Pagh
    Speaker: Lukas Tiago Bolte
  • 17.11.2017
    10:15 - 11:15
    ATI
    Isomorphism of bounded degree graphs
    Daniel Neuen
    something with isomorphism and bounded degree
  • 06.11.2017
    14:00 - 15:00
     
    The parameterized complexity of counting perfect matchings and other subgraphs
    Radu Curticapean
    Counting problems became a part of TCS at least since Valiant introduced the class #P and proved that counting perfect matchings is #P-complete. Polynomial-time algorithms for exact counting problems tend to be rare and curious, but even for the #P-hard problems, some progress can be made through the usual relaxations studied in TCS. Among those, this talk will cover the parameterized complexity of counting problems, as introduced by Flum and Grohe, and independently by McCartin. One part of the talk will focus on the complexity of counting perfect matchings, a problem studied in algebra, combinatorics, and statistical physics. We discuss how this problem reacts to structural parameters from graph minor theory like the genus, the apex number and the Hadwiger number. This contains some algorithmic results, but also conditional lower bounds under the exponential-time hypothesis ETH and its stronger sibling SETH. We also consider the problems of counting general subgraphs H in a host graph G, this time parameterized by the size of H. This gives rise to the problems #Sub(C) for fixed graph classes C: Given inputs H and G, where H is from C, count the H-copies in G. We show a dichotomy theorem for these problems, together with recently found connections to a framework developed by Lovász. The talk is based on several works, some of which involved Holger Dell, Dániel Marx, and Mingji Xia.
  • 03.11.2017
    10:15 - 11:15
     
    Isomorphism of Hypergraphs and Relational Structures
    Daniel Wiebking
  • 03.11.2017
    10:15 - 11:15
     
    Isomorphism of Hypergraphs and Relational Structures
    Daniel Wiebking
  • 27.10.2017
    10:15 - 11:15
     
    Uniformization Problems for Synchronizations of Relations on Words
    Sarah Winter
    A uniformization of a binary relation is a function that is contained in the relation and has the same domain as the relation. The synthesis problem asks for effective uniformization for classes of relations and functions that can be implemented in a specific way. We consider the synthesis problem for regular relations over finite words (also called automatic or synchronized rational relations) by functions implemented by specific classes of sequential transducers. It is known that the problem ``Given a regular relation, does it have a uniformization by a subsequential transducer?'' is decidable in the two variants where the uniformization can either be implemented by an arbitrary subsequential transducer or it has to be implemented by a synchronous transducer. We prove the decidability of a generalization of these two problems in which the allowed input/output behavior of the subsequential transducer is specified by a synchronization language.
  • 27.10.2017
    13:30 - 14:15
     
    Preprocessing algorithms for the Graph Isomorphism Problem
    Lorena Reintgen
    We develop a new approach to solve the Graph Isomorphism Problem (GI) for input graphs G and H over the same vertex set V that are close with respect to permutation distance. We show that if the input pair of graphs have permutation distance at most k, then it is possible to construct in quadratic time an equivalent instance of size at most f(k), for a computable function f, and decide whether there exists an isomorphism from G to H. Our algorithm is thus a kernelization algorithm and can be used as a preprocessing step for inputs with low permutation distance. The algorithm consists of four steps. In the first step we find a relabeling on the vertices of the symmetric difference $G triangle H$ as to restrict the maximal degree within $G triangle H$. Next, we construct from the previous result (G',H) a subset of vertices that contains the set of vertices that have to be relabeled in order to identify G' with H. This result in turn is used to construct a smaller instance for Colored Graph Isomorphism. In the final step this colored instance is again transformed into an uncolored graph, which constitutes our kernel instance.
  • 20.10.2017
    10:00 - 11:00
     
    Graph Similarity and Approximate Isomorphism
    Gaurav Rattan
    The graph similarity problem, also known as approximate graph isomorphism or graph matching problem has been extensively studied in the machine learning community, but has not received much attention in the algorithms community. Given two graphs G,H with adjacency matrices A_G,A_H, a well-studied measure of similarity is the Frobenius distance dist(G,H):=min_P || A_G^P - A_H ||_F, where P ranges over all permutations of the vertex set of G, A_G^P denotes the matrix obtained from A_G by permuting rows and columns according to P, and ||M||_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by SIM (WSIM), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases. It is known that SIM (WSIM) is NP-hard: we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for this problem is best done in the framework of linear algebra. Our main result is a polynomial time algorithm for the special case of WSIM where both input matrices are positive semi-definite, have bounded-rank, and where one of the matrices has a bounded clustering number. The clustering number is a natural algorithmic parameter arising from spectral clustering techniques. We complement this result by showing NP-hardness for matrices of bounded rank and for positive-semidefinite matrices.
  • 06.10.2017
    11:00 - 11:30
     
    Learning Algorithms for Tree Automata
    Patrick Smandzich
    Master's thesis presentation
  • 04.10.2017
    14:00 - 15:00
     
    A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry
    Pascal Schweitzer
    The paper develops a new technique to extract a characteristic subset from a random source that repeatedly samples from a set of elements. Here a characteristic subset is a set that when containing an element contains all elements that have the same probability. With this technique at hand the paper looks at the special case of the tournament isomorphism problem that stands in the way towards a polynomial-time algorithm for the graph isomorphism problem. Noting that there is a reduction from the automorphism (asymmetry) problem to the isomorphism problem, a reduction in the other direction is nevertheless not known and remains a thorny open problem. Applying the new technique, we develop a randomized polynomial-time Turing-reduction from the tournament isomorphism problem to the tournament automorphism problem. This is the first such reduction for any kind of combinatorial object not known to have a polynomial-time solvable isomorphism problem
  • 29.09.2017
    10:00 - 10:30
     
    Anfragebearbeitung mit konstanter Verzögerung
    Mario Jörres
    Das Kolloquium gibt einen Überblick über einige Ergebnisse bezüglich der Bearbeitung von Datenbankanfragen. Dabei beschränken wir uns auf die Klasse der konjunktiven Anfragen, da eine Reihe von bekannten NP-vollständigen Problemen als solche ausgedrückt werden kann, und stellen eine alternative Betrachtungsweise für die Komplexität des Auswertungsproblems solcher Anfragen vor. Wir nehmen an, es sei nicht notwendig, alle Antworten auf eine Anfrage zugleich zu erhalten, sondern es genügt, diese mit konstanter Verzögerung zwischen zwei aufeinanderfolgenden Antworten auszugeben, nachdem eine Vorverarbeitung in linearer Zeit stattfand. Dann kann man die Komplexität des Aufzählungsproblems anhand der Dauer der Vorverarbeitung und der Verzögerung betrachten.
  • 29.09.2017
    10:45 - 11:15
     
    Algorithmic aspects of pfaffian orientations
    Laurids Vollmann
    In this thesis we will examine the current research concerning the calculation of pfaffian orientations on different classes of graphs. Pfaffian orientations assign a direction to each edge in an undirected graph in a specific way and allow us to efficently calculate the amount of perfect matchings. Not every graph has a pfaffian orientation and for most graphs finding one is hard. We will also briefly present some polynomial-time equivalent problems.
  • 29.09.2017
    11:30 - 12:00
     
    Hashing Techniques for Computing Frequency Moments (Bachelor, Deutscher Vortrag)
    Yannick Epstein
    Randomized hashing is a fundamental part of approximating frequency mo- ments of data streams. To approximate the second frequency moment of a data stream, a strongly 4-universal family of hash functions is mandatory to give strong guarantees of the returned estimation’s accuracy. When implementing these approximation algo- rithms, arguments against using a strongly 4-universal family of hash functions are the need for shorter runtime or only having access to few random bits. We evaluate ex- perimentally the effects of using different hashing schemes to approximate the second frequency moment of real data streams. We obtain that universal, strongly 2-universal hashing, and a strongly 3-universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4-universal hashing.
  • 29.09.2017
    12:15 - 12:45
     
    Lower Bounds for Parallel Query Processing
    Joshua Fürste
    Conjunctive queries represent an important subset of queries issued on relational databases. We study the problem of computing conjunctive queries over large distributed databases. Using the structures of a query Q and the skew in the data, we take a look at the amount of communication required over one or multiple communication rounds, that is required to compute Q.
  • 29.09.2017
    10:00 - 10:30
     
    Anfragebearbeitung mit konstanter Verzögerung
    Mario Jörres
    Das Kolloquium gibt einen Überblick über einige Ergebnisse bezüglich der Bearbeitung von Datenbankanfragen. Dabei beschränken wir uns auf die Klasse der konjunktiven Anfragen, da eine Reihe von bekannten NP-vollständigen Problemen als solche ausgedrückt werden kann, und stellen eine alternative Betrachtungsweise für die Komplexität des Auswertungsproblems solcher Anfragen vor. Wir nehmen an, es sei nicht notwendig, alle Antworten auf eine Anfrage zugleich zu erhalten, sondern es genügt, diese mit konstanter Verzögerung zwischen zwei aufeinanderfolgenden Antworten auszugeben, nachdem eine Vorverarbeitung in linearer Zeit stattfand. Dann kann man die Komplexität des Aufzählungsproblems anhand der Dauer der Vorverarbeitung und der Verzögerung betrachten.
  • 29.09.2017
    10:45 - 11:15
     
    Algorithmic aspects of pfaffian orientations
    Laurids Vollmann
    In this thesis we will examine the current research concerning the calculation of pfaffian orientations on different classes of graphs. Pfaffian orientations assign a direction to each edge in an undirected graph in a specific way and allow us to efficently calculate the amount of perfect matchings. Not every graph has a pfaffian orientation and for most graphs finding one is hard. We will also briefly present some polynomial-time equivalent problems.
  • 29.09.2017
    11:30 - 12:00
     
    Hashing Techniques for Computing Frequency Moments (Bachelor, Deutscher Vortrag)
    Yannick Epstein
    Randomized hashing is a fundamental part of approximating frequency mo- ments of data streams. To approximate the second frequency moment of a data stream, a strongly 4-universal family of hash functions is mandatory to give strong guarantees of the returned estimation’s accuracy. When implementing these approximation algo- rithms, arguments against using a strongly 4-universal family of hash functions are the need for shorter runtime or only having access to few random bits. We evaluate ex- perimentally the effects of using different hashing schemes to approximate the second frequency moment of real data streams. We obtain that universal, strongly 2-universal hashing, and a strongly 3-universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4-universal hashing.
  • 29.09.2017
    12:15 - 12:45
     
    Lower Bounds for Parallel Query Processing
    Joshua Fürste
    Conjunctive queries represent an important subset of queries issued on relational databases. We study the problem of computing conjunctive queries over large distributed databases. Using the structures of a query Q and the skew in the data, we take a look at the amount of communication required over one or multiple communication rounds, that is required to compute Q.
  • 28.09.2017
    11:00 - 12:00
     
    A comparison of algorithms for games on pushdown automata and context-free games
    Michael Mutert
    Bachelor Kolloquium
  • 28.09.2017
    11:00 - 12:00
     
    A comparison of algorithms for games on pushdown automata and context-free games
    Michael Mutert
    Bachelor Kolloquium
  • 26.09.2017
    10:00 - 11:00
     
    Succinct Counting and Progress Measures for Solving Infinite Games// Katrin Dannert
    The talk will be given in English.
  • 26.09.2017
    11:00 - 12:00
     
    Verfahren zur Übersetzung von regulären Ausdrücken in endliche Automaten
    Daniel Schmitz