Termine Vorträge (Archiv)

Treffer 1 - 135 von 135 Ergebnissen

  • Termin
     
    Titel
  • 17.10.2019
    10:00 - 10:30
    BSc
    Comparing learning algorithms for regular expressions from positive examples
    Konrad Ostrowski
  • 17.10.2019
    10:45 - 11:15
    BSc
    A comparison of algorithms for automata learning on sparse data
    Caspar Zecha
  • 16.09.2019
    11:00 - 11:30
     
    The Complexity of First-Order Model Checking on Graphs of Bounded Tree Depth
    Jonathan du Mesnil de Rochemont
    In this talk, we discuss algorithmic meta-theorems for graphs of bounded tree-depth. Tree-Depth is a graph invariant also known as vertex ranking number and minimum elimination tree height, which captures, intuitively speaking, how much a graph resembles a star graph. We present a result due to Chen and Flum stating that the model-checking problem for FO parameterized by the length of the formula is in para-AC0 if the inputs are limited to any class of graphs of bounded tree-depth. para-AC0 can be viewed as the complexity class of parameterized problems that are decidable by polynomial-size constant-depth circuit families with arbitrary fan-in after a precomputation on the parameter. An important ingredient in the proof is the following characterization: We show that the model-checking problem for FO on any class of structures is in para-AC0 if and only if FO has an effective generalized quantifier elimination on that class. We then show that FO has such an effective generalized quantifier elimination on classes of graphs of bounded tree-depth to conclude the proof.
  • 16.09.2019
    11:45 - 12:15
     
    Data structures for approximate membership queries
    Razvan Manea
  • 09.09.2019
    14:00 - 15:00
     
    Representations of Correlated Probabilistic Databases
    Nils Freyer
    As an extension of Codd's relational data model, probabilistic databases were discussed in the literature when the relational data model became popular in the 1980's. The studies of probabilistic databases were motivated by errors in the data collection process and designed as a generalisation of the relational data model that is able to integrate probabilistic data into relational data. Today, the amount of data and information is growing strictly, which causes a lot of research in information extraction and efforts in representing the extracted information. One can imagine that representing correlated probabilistic data is not trivial. We will present the most common representation systems for probabilistic data and examine their properties. Afterwards, we will construct translations between the representation systems to draw conclusions on their relationships.
  • 28.06.2019
    10:00 - 11:00
     
    Sixth talk ATI seminar
    Anton Pirogov
  • 21.06.2019
    10:00 - 11:00
     
    Fourth talk ATI seminar
    Patrick Landwehr
  • 14.06.2019
    10:00 - 11:00
     
    Third talk ATI seminar
    Daniel Wiebking
  • 31.05.2019
    10:00 - 11:00
     
    Second talk ATI seminar
    Daniel Neuen
  • 31.05.2019
    10:00 - 11:00
     
    Second talk ATI seminar
    Daniel Neuen
  • 24.05.2019
    10:00 - 11:00
     
    First talk ATI seminar
    Jan Böker
  • 23.05.2019
    13:00 - 14:00
     
    The Weisfeiler-Leman Dimension of Graphs of Bounded Treedepth
    Luca Oeljeklaus
    In this talk we discuss the dimension of the Weisfeiler-Leman (WL) algorithm, which is a combinatorial algorithm used as a subroutine for graph isomorphism testing, in terms of treedepth, a graph invariant also referred to as minimum elimination tree height or vertex ranking number. More precisely, we prove upper and lower bounds on the WL-dimension of graphs of bounded treedepth by using two results from Cai, Fürer, and Immerman. In our proof to show that every graph of treedepth at most k is identified by the (k-1)-dimensional WL-algorithm, we use the fact that the (k-1)-dimensional WL-algorithm identifying a graph is equivalent to Spoiler having a winning strategy for the C_k-pebble game between a graph of treedepth at most k and any other non-isomorphic graph. From there we develop an inductive winning strategy for Spoiler over the treedepth of the graph. In our proof to show that there exists a family of pairs of graphs of treedepth k for arbitrarily large k such that the (k/25)-dimensional WL-algorithm does not distinguish them, we apply the CFI-graph construction to a family of graphs with large separators and then prove an upper bound on the treedepth of the resulting pairs of graphs.
  • 25.04.2019
    10:30 - 11:30
     
    Anytime Approximation in Probabilistic Databases via Scaled Dissociations
    Floris Geerts
    Speeding up probabilistic inference remains a key challenge in probabilistic databases (PDBs) and the related area of statistical relational learning (SRL). Since computing probabilities for query answers is #P-hard, even for fairly simple conjunctive queries, both the PDB and SRL communities have proposed a number of approximation techniques over the years. The two prevalent techniques are either (i) MCMC-style sampling or (ii) branch-and-bound (B&B) algorithms that iteratively improve model-based bounds using a combination of variable substitution and elimination. In this talk, I present a new anytime B&B approximation scheme that encompasses all prior model-based approximation schemes proposed in the PDB and SRL literature. The approach relies on the idea of “scaled dissociations” which can improve both the upper and lower bounds of existing model-based algorithms. Here, in each iteration, a gradient-descent based optimization method finds the best scaled dissociation bounds after which Shannon expansion is performed. When applied to the well-studied problem of evaluating self-join-free conjunctive queries over tuple-independent PDBs, a consistent reduction in approximation error is experimentally observed. This is joint work with Wolfgang Gatterbauer, Peter Ivanov, Martin Theobald and Maarten Van den Heuvel and will be presented at the SIGMOD 2019 Conference.
  • 17.04.2019
    11:00 - 11:45
    BSc
    Interactive Proof Systems for Counting Subgraphs
    Markus Baumann
    We provide an introduction to interactive proof systems, which describe two-party games between computational agents. Double efficiency denotes the practice of limiting both parties to efficient computation. We present in detail the recently published, doubly-efficient interactive clique counting protocol of Oded Goldreich and Guy N. Rothblum. Contrary to previous proof systems, that use the sum-check protocol, this one keeps the intuition of counting cliques intact, as it works by iteratively transforming them into smaller clique counting problems. Their work helps us see the applicability of interactive proof systems to tractable problems, and the advantages of double efficiency.
  • 29.03.2019
    10:30 - 11:30
    BSc
    Space Complexity of Regular Languages in the Sliding Window Data Stream Model
    Philipp Selz
  • 22.02.2019
    10:00 - 11:00
    ATI
    On the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
    Sandra Kiefer
    The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism test called the Weisfeiler-Leman algorithm, the WL dimension can also be characterised in terms of the number of variables that is required to describe the graph up to isomorphism in first-order logic with counting quantifiers.
    It is known that the WL dimension is upper-bounded for all graphs that exclude some fixed graph as a minor. However, the bounds that can be derived from this general result are astronomic. Only recently, it was proved that the WL dimension of planar graphs is at most 3. In this talk, I present some of the techniques from our recent proof that the WL dimension of graphs embeddable in a surface of Euler genus g is at most 4g + 3. This is joint work with Martin Grohe.
  • 08.02.2019
    10:00 - 11:00
    ATI
    The WL-dimension of graphs of bounded rank width
    Daniel Neuen
    We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3k+4) is a complete isomorphism test for the class of all graphs of rank width at most k. Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width. It was known that isomorphism of graphs of rank width k is decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running time n^{f(k)} for a non-elementary function f. Our result yields an isomorphism test for graphs of rank width k running in time n^{O(k)}. Another consequence of our result is the first polynomial time canonisation algorithm for graphs of bounded rank width. If time permits I will also speak about our second result that fixed-point logic with counting captures PTIME on the class of graphs of rank width at most k.
  • 24.01.2019
    10:00 - 10:30
    BSc
    A neural algorithm for similarity search
    Christian Blumenthal
  • 24.01.2019
    11:00 - 11:45
    MSc
    State Space Reduction For Parity Automata
    Andreas Tollkötter
  • 18.01.2019
    10:00 - 11:00
    ATI
    Definining Branch Decompositions in MSO
    Maya Frickenschmidt
  • 14.12.2018
    10:00 - 11:00
    ATI
    Color Refinement and Graph Neural Networks
    Martin Ritzert
    In this talk we show that the expressive power of the 1-dimensional Weisfeiler Leman algorithm (color refinement) is exactly as powerful as the emerging graph neural networks. Joint work with Martin Grohe and Gaurav Rattan
  • 12.12.2018
    11:00 - 11:45
    BSc
    Spektrale Graphähnlichkeit und Dominanz
    Athena Riazsadri
    Im Rahmen dieser Arbeit werden die Probleme der spektralen Graphdominanz (GD) und des spektralen Graphähnlichkeit (SGS) vorgestellt. Anstatt etwa die Anzahl der nicht gematchten Kanten zu vergleichen, werden Graphen aufgrund ihrer Eigenwerte und Laplacematrizen verglichen. Damit bietet die hier vorgestellte Lösung im Gegensatz zu anderen Lösungsansätzen zum Graphähnlichkeitsproblem die Möglichkeit, Graphen aufgrund ihrer Funktionalität zu vergleichen, was wiederum Anwendung gerade in der Biologie (Proteinnetzwerke) finden könnte. Die Hauptergebnisse dieser Arbeit sind ein NP-Schwere-Beweis für GD und ein κ^4-Approximationsalgorithmus für SGS auf zwei Graphen beschränkten Grades. Dieser Algorithmus läuft in polynomieller Zeit für ein konstantes κ.
  • 07.12.2018
    10:00 - 11:00
    ATI
    Learning FOCN(P) Definable Concepts over Structures of Small Degree
    Steffen van Bergerem
  • 30.11.2018
    10:00 - 11:00
    ATI
    Universal graphs for parity and mean-payoff games
    Nathanaël Fijalkow
    I will present a new tool for understanding games on graphs called universal graphs. They can be used to construct algorithms for solving games such as parity games and mean-payoff games. The goals of this talk are to: * introduce the notion of universal graphs and their applications to games * give a simple and unified presentation of all three quasipolynomial time algorithms for parity games * construct new algorithms for mean-payoff games * show tight lower bounds for the construction of algorithms in this framework for both parity and mean-payoff games
  • 30.11.2018
    10:00 - 11:00
    ATI
    Universal graphs for parity and mean-payoff games
    Nathanaël Fijalkow
    I will present a new tool for understanding games on graphs called universal graphs. They can be used to construct algorithms for solving games such as parity games and mean-payoff games. The goals of this talk are to: * introduce the notion of universal graphs and their applications to games * give a simple and unified presentation of all three quasipolynomial time algorithms for parity games * construct new algorithms for mean-payoff games * show tight lower bounds for the construction of algorithms in this framework for both parity and mean-payoff games
  • 23.11.2018
    10:30 - 11:30
    ATI
    Detecting small subgraphs using the exterior algebra
    Holger Dell
    Color-coding is a popular technique to detect and to approximately count short paths and other subgraphs of bounded treewidth. In this talk, we will discuss Extensor-coding, a natural approach to such subgraph detection problems that turns out to generalize and in some cases improve upon the running time achieved by Color-coding. Based on joint work with Cornelius Brand and Thore Husfeldt.
  • 16.11.2018
    10:00 - 11:00
    ATI
    Structural Similarity and Homomorphism Counts
    Jan Böker
  • 10.11.2018
    00:00 - 03:00
     
    Wissenschaftsnacht der Professoren mit DJ Prof. Grohe
    DJ Prof. Grohe
  • 09.11.2018
    10:30 - 11:30
    ATI
    A unifying method for the design of algorithms canonizing combinatorial objects
    Daniel Wiebking
    We devise a unified framework for the design of canonization algorithms. Using hereditarily finite sets, we define a general notion of combinatorial objects that includes graphs, hypergraphs, relational structures, codes, permutation groups, tree decompositions, and so on. Our approach allows for a systematic transfer of the techniques that have been developed for isomorphism testing to canonization. We use it to design a canonization algorithm for general combinatorial objects. This result gives new fastest canonization algorithms with an asymptotic running time matching the best known isomorphism algorithm for the following types of objects: hypergraphs, hypergraphs of bounded color class size, permutation groups (up to permutational isomorphism) and codes that are explicitly given (up to code equivalence).
  • 26.10.2018
    14:15 - 15:15
     
    Explaining and Representing Novel Concepts With Minimal Supervision
    Zeynep Akata (University of Amsterdam)
    Clearly explaining a rationale for a classification decision to an end-user can be as important as the decision itself. Existing approaches for deep visual recognition are generally opaque and do not output any justification text; contemporary vision-language models can describe image content but fail to take into account class-discriminative image properties which justify visual predictions. In this talk, I will present my past and current work on Zero-Shot Learning, Vision and Language for Generative Modeling and Explainable Artificial Intelligence where we show (1) how to generalize image classification models to cases when no visual training data is available, (2) how to generate images and image features using detailed visual descriptions, and (3) how our models focus on discriminating properties of the visible object, jointly predict a class label, explain why/not the predicted label is chosen for the image.
  • 23.10.2018
    16:15 - 17:00
     
    Polyregular functions
    Mikołaj Bojańczyk
    I will describe a class of string-to-string transducers, which goes beyond rational or regular functions, but still shares many of their good properties (e.g. the inverse image of a regular language is regular). Unlike many string-to-string transducer models (including sequential, rational and regular transducers), which have linear size increase, the the new class (called polyregular functions) has polynomial size increase. The main selling point of the polyregular functions is that they admit numerous equivalent descriptions:  automata with pebbles; (b) a fragment of lambda calculus; (c) a fragment of for-programs; and (d) compositions of certain atomic functions, such as reverse or a form of string squaring. Also, most likely (this is still ongoing work): (e) mso string-to-string interpretations.
  • 10.10.2018
    10:00 - 10:45
    MSc
    Spectral graph similarity
    Timo Gervens
  • 05.10.2018
    11:00 - 11:45
    BSc
    Weighted Symmetric Model Counting for Two Variable Logic
    Tobias Schleifstein
    The first order model counting problem (FOMC) asks for the number of models of a FO-sentence with the domain of given size n. The weighted first order model counting problem (WFOMC) additionally assigns a weight to every tupel of the models' relations. In the symmetric variant, which is mainly studied in this thesis, we have to assign the same weights to all tupels of the same relation. We review the results for tractability of the symmetric WFOMC for two-variable logic and three-variable logic. In particular we discuss the data complexity, i.e., the complexity of computing the problems with only the size n of the domain as an input and the formula and weights fixed. It has been shown that the WFOMC is computable in polynomial time for FO² and an extension, but #P_1-complete for FO³.
  • 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
  • 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
  • 13.09.2017
    11:00 - 12:00
     
    A finitary analogue of the downward Lowenheim-Skolem property
    Abhisekh Sankaran
    We present a model-theoretic property of finite structures, that can be seen to be a finitary analogue of the well-studied downward Lowenheim-Skolem property from classical model theory. We call this property the *equivalent bounded substructure property*, denoted EBSP. Intuitively, EBSP states that a large finite structure contains a small ``logically similar'' substructure, where logical similarity means indistinguishability with respect to sentences of FO/MSO having a given quantifier nesting depth. It turns out that this simply stated property is enjoyed by a variety of classes of interest in computer science: examples include regular languages of words, trees (unordered, ordered, ranked or partially ranked) and nested words, and various classes of graphs, such as cographs, graph classes of bounded tree-depth, those of bounded shrub-depth and m-partite cographs. Further, EBSP remains preserved in the classes generated from the above using various well-studied operations, such as complementation, transpose, the line-graph operation, disjoint union, join, and various products including the Cartesian and tensor products. All of the aforementioned classes admit natural tree representations for their structures. We use this fact to show that the small and logically similar substructure of a large structure in any of these classes, can be computed in time linear in the size of the tree representation of the structure, giving linear time fixed parameter tractable (f.p.t.) algorithms for checking FO/MSO definable properties of the large structure. We conclude by presenting a strengthening of EBSP, that asserts ``logical self-similarity at all scales'' for a suitable notion of scale. We call this the *logical fractal* property and show that most of the classes mentioned above are indeed, logical fractals.
  • 01.09.2017
    10:00 - 11:00
     
    FO Model Checking on some Dense Graph Classes using FO-Interpretations
    Dimitri Rusin
  • 01.09.2017
    10:00 - 11:00
     
    FO Model Checking on some Dense Graph Classes using FO-Interpretations
    Dimitri Rusin
  • 31.08.2017
    12:00 - 12:30
     
    Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TC-Logiken
    Yannic Rohde
  • 31.08.2017
    12:00 - 12:30
     
    Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TC-Logiken
    Yannic Rohde
  • 30.08.2017
    11:00 - 12:00
     
    Homomorphisms are a good basis for counting small subgraphs
    Holger Dell
    We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. Using the framework of graph motif parameters, we obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G: For graphs H on k edges, we show how to count subgraph copies of H in time k^{O(k)}⋅n^{0.174k+o(k)} by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k+c) time for k-edge matchings or O(n0.46k+c) time for k-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating f∈C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class H, we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions. Joint work with Radu Curticapean and Dániel Marx
  • 30.08.2017
    11:00 - 12:00
     
    Homomorphisms are a good basis for counting small subgraphs
    Holger Dell
    We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. Using the framework of graph motif parameters, we obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G: For graphs H on k edges, we show how to count subgraph copies of H in time k^{O(k)}⋅n^{0.174k+o(k)} by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k+c) time for k-edge matchings or O(n0.46k+c) time for k-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating f∈C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class H, we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions. Joint work with Radu Curticapean and Dániel Marx
  • 25.08.2017
    15:00 - 16:00
     
    Decomposition Techniques for the Graph Isomorphism Problem
    Oliver Feith
    Closing the gap between the lower and upper bounds for the computational complexity of the Graph Isomorphism problem still is a big challenge for mathematicians and computer scientists. While resolving this problem in the general case seems out of reach, substantial progress has been made for restricted graph classes such as planar graphs. In particular, planar graph isomorphism has recently been shown to be in L (and thus is L-complete) by Datta, Limaye, Nimbhorkar, Thierauf and Wagner. We generalize the decomposition technique used in their result to work with minor-closed graph classes whose 3-connected members fulfill a fixability condition and admit a log-space canonization algorithm.
  • 24.08.2017
    10:30 - 10:30
     
    Weisfeiler-Lehman Kernels for Deep Neural Nets
    Jan Tönshoff
    Many real world applications, such as analysing social networks or internet traffic, require the analysis of large sets of graph structured data. Teaching neural networks to recognise patterns in graphs seems like an intuitive way of simplifying these tasks. To achieve this, we need to represent graphs as vectors in a suitable way that enables neural networks to find patterns in the underlying structure of the graphs. In this thesis we examine the performance of a vector representation for graphs obtained from the Weisfeiler-Lehman subtree kernel as an input for neural networks. We test the performance on standard graph classification tests with datasets based in bioinformatics. The results are shown to be competitive with those of state-of-the-art graph kernels for support vector machines. To solve scalability problems, we show that the size of these vectors can be reduced significantly without lowering the learning performance. Additionally, we show that the adjacency matrix is not a suitable vector representation of graphs when using neural networks. While the networks are able to learn some patterns with these inputs, the learning performance is significantly lower than for the vectors from the Weisfeiler-Lehman subtree kernel. Before we make these observations we provide brief introductions into Weisfeiler-Lehman graph kernels and neural networks.
  • 14.08.2017
    11:00 - 12:00
     
    Algorithms computing the fixing number of planar graphs
    Daniel Mock
    Fixing sets are a way to break symmetries and determine automorphisms of a graph. The fixing number of a graph G is the smallest cardinality of a set of vertices S such that only the trivial automorphism of G fixes every vertex in S. In this talk I present an algorithm for computing the fixing number of a planar graph by decomposing it into its triconnected components and by using bottom-up recursion upon these components. For this to work I introduce a generalization of the fixing number, the so-called vertex-arc fixing number: in addition to vertices, the fixing set may also contain edges and arcs of the graph. The provided algorithm can be applied to any minor-closed graph class that allows isomorphism testing and computing the vertex-arc fixing number of its triconnected graphs in polynomial time.
  • 28.07.2017
    10:15 - 11:45
    ATI
    Fixed-Parameter Tractable Canonization for Graphs of Bounded Treewidth
    Daniel Wiebking
  • 27.07.2017
    11:00 - 12:00
     
    Comparing the power of advice strings
    Gaëtan Douéneau
    We investigate a certain notion of comparison between infinite words. In a general way, if M is a model of computation (e.g. Turing machines) and C a class of objects (e.g. languages), the complexity of an infinite word w can be measured with respect to the objects from C that are presentable with machines from M using w as an advice. In our case, the model is finite automata and the objects are either recognized languages or presentable structures, known respectively as advice regular languages and advice automatic structures. This leads to several different classifications that are studied in detail; logical and computational equivalent characterizations are derived. Our main results explore the connections between classes of advice automatic structures, $MSO$-transductions and two-way transducers.
  • 21.07.2017
    10:15 - 11:45
    ATI
    An Improved Distributed Algorithm for Maximal Independent Set
    work by Mohsen Ghaffari
  • 20.07.2017
    14:00 - 15:00
     
    Graph Classification: Kernels and Beyond
    Christopher Morris
    Graph kernels are a popular approach to graph comparison and at the heart of many machine learning applications in bioinformatics, imaging, and social-network analysis. In this talk we shall first present a graph kernel that takes "local" and "global" graph properties into account. Thereto, we develop a "local" version of the $k$-dimensional Weisfeiler-Lehman algorithm. In order to make our kernel scalable, we devise a randomized version of the kernel with provable approximation guarantees using conditional Rademacher averages. On bounded-degree graphs, it can even be computed in constant time. In the second part, we will give an overview about recent progress in the area of graph classification and graph regression via so called "deep learning".
  • 19.07.2017
    16:00 - 17:00
     
    Stochastic dominance and the bijective ratio of online algorithms
    Spyros Angelopoulos
    Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. Accordingly this holds for bijective analysis, which can be interpreted as stochastic dominance assuming the uniform distribution over requests. These techniques have been applied to some online problems, and have provided a clear separation between algorithms whose performance varies significantly in practice. However, there are situations in which they are not readily applicable due to the fact that they stipulate a stringent relation between the compared algorithms. In this presentation, we propose remedies for these shortcomings. Our contribution is two-fold. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the bijective ratio as a natural extension of (exact) bijective analysis. This renders the concept of bijective analysis (and that of stochastic dominance) applicable to all online problems, and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous k-server problem on metrics such as the line, the circle, and the star. Joint work with Marc Renault and Pascal Schweitzer
  • 18.07.2017
    15:00 - 15:30
     
    Fractional Hypertree Decompositions
    Steffen van Bergerem
  • 07.07.2017
    10:15 - 11:15
    ATI
    Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
    work by Ran Raz
  • 07.07.2017
    11:15 - 12:15
     
    Enumerating Tree Decompositions: Why and How
    Benny Kimelfeld
    Many intractable problems on graphs have efficient solvers when graphs are trees or forests. Tree decompositions often allow to apply such solvers to general graphs by grouping nodes into bags laid out in a tree structure, thereby decomposing the problem into the sub-problems induced by the bags. This approach has applications in a plethora of domains, partly because it allows the optimize inference on probabilistic graphical models, as well as evaluation of database queries. Nevertheless, a graph can have exponentially many tree decompositions and finding an ideal one is challenging, for two main reasons. First, the measure of goodness often depends on subtleties of the specific application at hand. Second, theoretical hardness is met already for the simplest measures such as the maximal size of bag (a.k.a. “width”). Therefore, we explore the approach of producing a large space of high-quality tree decompositions for the application to choose from. I will describe our application of tree decompositions in the context of “worst-case optimal” joins --- a new breed of in-memory join algorithms that satisfy strong theoretical guarantees and were found to feature a significant speedup compared to traditional approaches. Specifically, I will explain how this development led us to the challenge of enumerating tree decompositions. Then, I will describe a novel enumeration algorithm for tree decompositions with a theoretical guarantee on the delay (the time between consecutive answers), and an experimental study thereof (on graphs from various relevant domains). Finally, I will describe recent results that provide guarantees on both the delay and the quality of the generated tree decompositions. The talk will be based on papers that appeared in EDBT 2017 and PODS 2017, co-authored with Nofar Carmeli, Yoav Etsion, Oren Kalinsky and Batya Kenig.
  • 04.07.2017
    16:00 - 17:00
     
    The hardness of embedding grids and walls
    Yijia Chen
    The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph G from some class K of ``pattern graphs'' can be embedded into a given graph H (that is, is isomorphic to a subgraph of H) is fixed-parameter tractable if K is a class of graphs of bounded tree width and W[1]-complete otherwise. In this talk, I will explain the background and history of this conjecture, and also our recent result that the embedding problem is W[1]-complete if K is the class of all grids or the class of all walls. This is joint work with Martin Grohe and Bingkai Lin.
  • 04.07.2017
    17:00 - 18:00
     
    Testing logically defined properties on structures of bounded degree
    Isolde Adler
    Property testing (for a property P) asks for a given input, whether it has property P, or is "far" from having that property. A "testing algorithm" is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as "extremely efficient", making them relevant in the context of big data. We extend the bounded degree model of property testing from graphs to relational structures, and we show that every property definable in first-order logic is testable with a constant number of queries in constant time. On structures of bounded tree-width, monadic second-order logic can be tested with a constant number of queries in polylogarithmic time. This is joint work with Frederik Harwath.
  • 30.06.2017
    10:15 - 11:45
    ATI
    Regular Separability of One Counter Automata
    work by Wojciech Czerwiński and Sławomir Lasota
  • 30.06.2017
    10:15 - 11:45
    ATI
    Regular Separability of One Counter Automata
    work by Wojciech Czerwiński and Sławomir Lasota
  • 23.06.2017
    10:15 - 11:45
    ATI
    The 4/3 Additive Spanner Exponent Is Tight
    work by Amir Abboud and Greg Bodwin
  • 16.06.2017
    10:15 - 11:45
    ATI
    The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
    Sandra Kiefer
    We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in fixed- point logic with counting using at most 4 variables. The previously best known upper bounds for the dimension and number of variables were 14 and 15, respectively. First we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of any vertex-/arc-colored 3-connected graph belonging to this class. Then we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two correctly chosen vertices of a colored 3-connected planar graph followed by the 1-dimensional WL-algorithm produces the discrete vertex partition. This implies that the 3-dimensional WL-algorithm determines the orbits of a colored 3-connected planar graph. As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3. This is joint work with Ilia Ponomarenko and Pascal Schweitzer.
  • 02.06.2017
    10:15 - 11:45
    ATI
    A Purely Relational Language for Choiceless Computation
    Erkal Selman
  • 02.06.2017
    10:15 - 11:45
    ATI
    A Purely Relational Language for Choiceless Computation
    Erkal Selman
  • 30.05.2017
    10:30 - 11:30
     
    The Connection Between Visibly Pushdown and Operator Precedence Languages
    Mietze Tang
    Bachelor thesis final talk
  • 30.05.2017
    10:30 - 11:30
     
    The Connection Between Visibly Pushdown and Operator Precedence Languages
    Mietze Tang
    Bachelor thesis final talk
  • 19.05.2017
    10:15 - 11:45
    ATI
    Graph decompositions using MSO transductions
    Marlin Frickenschmidt
  • 17.05.2017
    15:30 - 16:30
     
    Answering database queries under updates
    Nicole Schweikardt
    Query evaluation is one of the most fundamental tasks in databases, and a vast amount of literature is devoted to the complexity of this problem. This talk will focus on query evaluation in the “dynamic setting”, where the database may be updated by inserting or deleting tuples. In this setting, an evaluation algorithm receives a query Q and an initial database D and starts with a preprocessing phase that computes a suitable data structure to represent the result of evaluating Q on D. After every database update, the data structure is updated so that it represents the result of evaluating Q on the updated database. The data structure shall be designed in such a way that it quickly provides the query result, preferably in constant time (i.e., independent of the database size). We focus on the following flavours of query evaluation. (1) Testing: Decide whether a given tuple t is contained in Q(D). (2) Counting: Compute the number of tuples that belong to Q(D). (3) Enumeration: Enumerate Q(D) with a bounded delay between the output tuples. Here, as usual, Q(D) denotes the k-ary relation obtained by evaluating a k-ary query Q on a relational database D. For Boolean queries, all three tasks boil down to (4) Answering: Decide if Q(D) is non-empty. Compared to the dynamic descriptive complexity framework introduced by Patnaik and Immerman (1997), which focuses on the expressive power of first-order logic on dynamic databases and has led to a rich body of literature, we are interested in the computational complexity of query evaluation. We say that a query evaluation algorithm is efficient if the update time is either constant or at most polylogarithmic in the size of the database. In this talk I want to give an overview of recent results in this area.
  • 12.05.2017
    10:15 - 11:45
    ATI
    Learning MSO-definable hypotheses on strings
    Martin Ritzert
  • 05.05.2017
    10:15 - 11:45
    ATI
    Tree Automata with Constraints for Infinite Trees
    Patrick Landwehr
  • 28.04.2017
    10:15 - 11:45
    ATI
    On the Expressiveness of Unfolding Proofs for Recursive Data Structures
    Christof Löding
    Unfolding proofs are a heuristic that is used for verifying properties of heap manipulating programs with recursively defined data structures (like lists or trees). The heuristic reduces the property to be verified to a finite set of quantifier formulas, which can be tested for satisfiability by an SMT solver. The quantifier formulas are basically obtained by instantiating (unfolding) the recursive definitions with concrete terms referring to heap elements. In this joint ongoing work with P. Madhusudan and Lucas Pena (University of Illinois Urbana-Champaign), we aim at understanding which properties can proven using this heuristic.
  • 25.04.2017
    10:30 - 11:30
     
    Complexity of cardinality problems for automata on infinite words
    Duc Thanh Tran
    Bachelor thesis final talk
  • 21.04.2017
    11:45 - 12:45
     
    Complexity of determinizing automata by pruning the transition relation
    Philip Tse
    Bachelor thesis final talk
  • 29.03.2017
    10:00 - 11:00
     
    Complexity of the Graph Homomorphism Problem
    Philipp Niemietz
  • 29.03.2017
    10:00 - 11:00
     
    Complexity of the Graph Homomorphism Problem
    Philipp Niemietz
  • 24.03.2017
    10:15 - 11:45
     
    Parity games in quasi-polynomial time
    Katrin Dannert
    The problem of deciding parity games is known to be in NP and in co-NP but it is unknown, whether it is solvable in polynomial time. Recently it has been shown that the problem can be solved both in quasipolynomial time and in FPT with the number of colours as the parameter. In order to obtain these runtimes, space- efficient winning statistics for a play are maintained by building up and combining "favourable" sequences whose lengths are powers of two. This yields an alternating polylogarithmic space algorithm, which can be translated both into a quasipolyno- mial time algorithm and an FPT algorithm. Based on the paper Deciding Parity Games in Quasipolynomial Time by Calude, Jain, Khoussainov, Li and Stephan
  • 20.03.2017
    11:00 - 12:00
     
    Properties of Limit Deterministic Büchi Automata
    Max Ohn
  • 20.03.2017
    12:00 - 13:00
     
    Uniformization of Rational Relations
    Yordan Manolov
  • 14.03.2017
    11:00 - 12:00
     
    Logiken mit Multiteam-Semantik
    Richard Wilke
    Klassische Logiken werden mit der so genannten Tarski-Semantik aus- gewertet. Dabei gibt eine Zuweisung den vorkommenden Variablen einer Formel ihre Bedeutung. Dieses Konzept st ̈oßt an seine Grenzen sobald man Abh ̈angigkeiten zwischen den Variablen ausdru ̈cken m ̈ochte. Verschiedene Logiken sind entwickelt worden um derartige Aussagen treffen zu k ̈onnen. Das ju ̈ngste Konzept ist die Team-Semantik. Man betrachtet dort zu ei- ner Formel eine Menge von Zuweisungen, die miteinander interagieren. So kann man beispielsweise die Aussage treffen, dass der Wert einer Variable y ausschließlich vom Wert der Variable x abh ̈angig ist. Ein Team kann als Datenbank betrachtet werden, wobei jede Zuweisung einen Eintrag repr ̈asentiert. In reellen Anwendungen kann es von großer Be- deutung sein, wie oft ein gewisser Eintrag vorkommt. Wir betrachtet daher Logiken mit Multiteam-Semantik, welche sich eben dieser Herausforderung stellen.
  • 03.03.2017
    10:15 - 11:15
     
    The First-Order Logic of Hyperproperties
    Martin Zimmermann
    We investigate the logical foundations of hyperproperties. Hyperproperties generalize trace properties, which are sets of traces, to sets of sets of traces. The most prominent application of hyperproperties is information flow security: information flow policies characterize the secrecy and integrity of a system by comparing two or more execution traces, for example by comparing the observations made by an external observer on execution traces that result from different values of a secret variable. In this paper, we establish the first connection between temporal logics for hyperproperties and first-order logic. Kamp's seminal theorem (in the formulation due to Gabbay et al.) states that linear-time temporal logic (LTL) is expressively equivalent to first-order logic over the natural numbers with order. We introduce first-order logic over sets of traces and prove that HyperLTL, the extension of LTL to hyperproperties, is strictly subsumed by this logic. We furthermore exhibit a fragment that is expressively equivalent to HyperLTL, thereby establishing Kamp's theorem for hyperproperties. Based on joint work with Bernd Finkbeiner (Saarland University).
  • 03.03.2017
    10:15 - 11:15
     
    The First-Order Logic of Hyperproperties
    Martin Zimmermann
    We investigate the logical foundations of hyperproperties. Hyperproperties generalize trace properties, which are sets of traces, to sets of sets of traces. The most prominent application of hyperproperties is information flow security: information flow policies characterize the secrecy and integrity of a system by comparing two or more execution traces, for example by comparing the observations made by an external observer on execution traces that result from different values of a secret variable. In this paper, we establish the first connection between temporal logics for hyperproperties and first-order logic. Kamp's seminal theorem (in the formulation due to Gabbay et al.) states that linear-time temporal logic (LTL) is expressively equivalent to first-order logic over the natural numbers with order. We introduce first-order logic over sets of traces and prove that HyperLTL, the extension of LTL to hyperproperties, is strictly subsumed by this logic. We furthermore exhibit a fragment that is expressively equivalent to HyperLTL, thereby establishing Kamp's theorem for hyperproperties. Based on joint work with Bernd Finkbeiner (Saarland University).
  • 17.02.2017
    10:15 - 11:15
     
    Compact graphs and the LP approach to GI
    Gaurav Rattan
    Using the LP formulation for GI, we describe the class of compact graphs, proposed by Tinhofer. Isomorphism testing for such graphs can be done efficiently, using the linear program for GI. The recognition problem for such graphs remains open. Towards a partial understanding of this class, we describe some connections of this class with Color Refinement and Individualization techniques.
  • 03.02.2017
    10:15 - 11:15
    ATI
    An exponential lower bound for Individualization/Refinement algorithms for Graph Isomorphism
    Daniel Neuen
    The individualization and refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, it provides the only methods for isomorphism testing which are also viable for practical uses. From the theoretical point of view, no meaningful lower bounds on the worst case complexity of these tools are known. In fact, it is an open question whether these simple methods might provide similar upper bounds than existing algorithms combining complex group theoretic and combinatorial tools. In this work we give a negative answer to this question and construct a family of graphs that provides an exponential lower bound for methods based on the individualization and refinement paradigm. Other than previous constructions like Miyazaki graphs, our construction is immune to changing the cell selector or invariants used within the algorithm. Furthermore, our graphs also provide exponential lower bounds in the case where k-dimensional Weisfeiler Leman is used for refinement instead of color refinement (i.e. 1-dimensional Weisfeiler Leman) and the arguments even work when the automorphism group is initially known to the algorithm. In particular, under some moderate assumptions, our lower bounds are independent from which heuristics are used for cell selection, node invariants and automorphism detection.
  • 03.02.2017
    10:15 - 11:15
    ATI
    An exponential lower bound for Individualization/Refinement algorithms for Graph Isomorphism
    Daniel Neuen
    The individualization and refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, it provides the only methods for isomorphism testing which are also viable for practical uses. From the theoretical point of view, no meaningful lower bounds on the worst case complexity of these tools are known. In fact, it is an open question whether these simple methods might provide similar upper bounds than existing algorithms combining complex group theoretic and combinatorial tools. In this work we give a negative answer to this question and construct a family of graphs that provides an exponential lower bound for methods based on the individualization and refinement paradigm. Other than previous constructions like Miyazaki graphs, our construction is immune to changing the cell selector or invariants used within the algorithm. Furthermore, our graphs also provide exponential lower bounds in the case where k-dimensional Weisfeiler Leman is used for refinement instead of color refinement (i.e. 1-dimensional Weisfeiler Leman) and the arguments even work when the automorphism group is initially known to the algorithm. In particular, under some moderate assumptions, our lower bounds are independent from which heuristics are used for cell selection, node invariants and automorphism detection.
  • 27.01.2017
    10:15 - 11:15
    ATI
    N-Memory Automata Over the Alphabet N
    Patrick Landwehr
    An automaton model for words over the alphabet of the natural numbers is presented - the so called N-memory automaton. We explain its close connection to MSO-logic and discuss its expressive power and closure properties. Additionally we show among other decidability results the solvability of the non-emptiness problem.
  • 20.01.2017
    10:15 - 11:15
    ATI
    Ramanujan Graphs in Polynomial Time
    Lars Beckers
  • 13.01.2017
    10:15 - 11:15
    ATI
    Differential Privacy
    Andreas Klinger
  • 13.01.2017
    14:15 - 15:15
     
    Extensions of First-Order Logic by Propositional Proof Systems
    Benedikt Pago
    Propositional proof systems such as Resolution or the Polynomial Calculus have been studied as approaches for solving computationally difficult problems, e.g. Graph Isomorphism. As this problem requires proofs of exponential size, this motivates the question of which problems have only polynomial proof complexity. We address this by analysing the expressive power of logics incorporating suitably restricted versions of Resolution and monomial-PC (a weaker variant of the Polynomial Calculus) which are guaranteed to produce polynomial-size proofs. It turns out that the power of these restricted proof systems can be described in terms of other well-known logics, namely we obtain equivalences with least fixed-point logic (LFP), existential least fixed-point logic (EFP) and fixed-point logic with counting (FPC).