
Date
Title

06/12/2019
10:00  11:00
ATI

29/11/2019
10:00  11:00
ATI
Fractional Sets, Fractional Decompositions, and Fractional TanglesEva Fluck

29/11/2019
10:00  11:00
ATI
Fractional Sets, Fractional Decompositions, and Fractional TanglesEva Fluck

22/11/2019
10:00  11:00
ATI
Ambiguity in Probabilistic Büchi AutomataAnton PirogovProbabilistic Büchi automata are a natural generalization of PFA to infinite words, but have been studied indepth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this talk I will present new classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical ωautomata.

20/11/2019
13:15  13:45
MSc
Algorithms for Maximum Matching Width
Yassin Bahloul

20/11/2019
15:00  15:30
BSc
The FineGrained Complexity of FirstOrder Properties
Louis Härtel
Based on the results by Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova and Ryan Williams, we break down the finegrained complexity of firstorder properties by analyzing their reduction from any modelchecking problem on a (k + 1)quantifier firstorder formula to the sparse version of kOrthogonal Vectors, and summarize their algorithmic improvements and consequences for common finegrained conjectures.

15/11/2019
10:00  11:00
ATI

25/10/2019
10:00  11:00
ATI
Tree automata with global constraints for infinite treesPatrick LandwehrWe study an extension of tree automata on infinite trees with global equality and disequality constraints. These constraints can enforce that all subtrees for which in the accepting run a state q is reached (at the root of that subtree) are identical, or that these trees differ from the subtrees at which a state q' is reached. We consider the closure properties of this model, its decision problems and its connection to logic.

24/10/2019
10:00  10:30
BSc
Regular Sensing for Nested Word Automta
Alina Ibach

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 FirstOrder Model Checking on Graphs of Bounded Tree Depth
Jonathan du Mesnil de Rochemont
In this talk, we discuss algorithmic metatheorems for graphs of bounded treedepth. TreeDepth 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 modelchecking problem for FO parameterized by the length of the formula is in paraAC0 if the inputs are limited to any class of graphs of bounded treedepth. paraAC0 can be viewed as the complexity class of parameterized problems that are decidable by polynomialsize constantdepth circuit families with arbitrary fanin after a precomputation on the parameter. An important ingredient in the proof is the following characterization: We show that the modelchecking problem for FO on any class of structures is in paraAC0 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 treedepth 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.

14/06/2019
10:00  10:30
ATI
A unifying method for the design of algorithms canonizing combinatorial objectsDaniel WiebkingWe 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).

31/05/2019
10:00  11:00
ATI
The Power of the WeisfeilerLeman Algorithm to Decompose GraphsDaniel NeuenThe WeisfeilerLeman procedure is a widelyused approach for graph
isomorphism testing, which iteratively computes an isomorphisminvariant
coloring of vertex tuples. Meanwhile, a fundamental tool in structural
graph theory, which is often exploited in approaches to tackle the graph
isomorphism problem, is the decomposition into bi and triconnected
components.
We prove that the 2dimensional WeisfeilerLeman algorithm implicitly
computes the decomposition of a graph into its triconnected components.
This means that the decomposition into triconnected components is "for
free" with respect to the dimension of the algorithm needed to
distinguish two graphs (assuming dimension at least 2).
This result implies that the kdimensional algorithm distinguishes
kseparators, i.e., ktuples of vertices that separate the graph, from
other vertex ktuples. As a byproduct, we also obtain insights about the
connectivity of constituent graphs of association schemes.
In an application of the results, we show the new upper bound of k on
the WeisfeilerLeman dimension of graphs of treewidth at most k. Using a
construction by Cai, Fürer, and Immerman, we also provide a new lower
bound that is asymptotically tight up to a factor of 2.
This is joint work with Sandra Kiefer.

31/05/2019
10:00  11:00
ATI
The Power of the WeisfeilerLeman Algorithm to Decompose GraphsDaniel NeuenThe WeisfeilerLeman procedure is a widelyused approach for graph
isomorphism testing, which iteratively computes an isomorphisminvariant
coloring of vertex tuples. Meanwhile, a fundamental tool in structural
graph theory, which is often exploited in approaches to tackle the graph
isomorphism problem, is the decomposition into bi and triconnected
components.
We prove that the 2dimensional WeisfeilerLeman algorithm implicitly
computes the decomposition of a graph into its triconnected components.
This means that the decomposition into triconnected components is "for
free" with respect to the dimension of the algorithm needed to
distinguish two graphs (assuming dimension at least 2).
This result implies that the kdimensional algorithm distinguishes
kseparators, i.e., ktuples of vertices that separate the graph, from
other vertex ktuples. As a byproduct, we also obtain insights about the
connectivity of constituent graphs of association schemes.
In an application of the results, we show the new upper bound of k on
the WeisfeilerLeman dimension of graphs of treewidth at most k. Using a
construction by Cai, Fürer, and Immerman, we also provide a new lower
bound that is asymptotically tight up to a factor of 2.
This is joint work with Sandra Kiefer.

24/05/2019
10:00  11:00
The Complexity of Homomorphism IndistinguishabilityJan BökerWe study the complexity of HomInd(F): for a class F of graphs, HomInd(F) denotes the problem of deciding whether two given graphs G and H are homomorphism indistinguishable over F, i.e., whether for every graph F' in F, the number of homomorphisms from F' to G equals the corresponding number from F' to H. We show that there is a polynomialtime decidable class F of graphs of bounded treewidth for which HomInd(F) is undecidable. Our second hardness result concerns the class K of complete graphs: We show that HomInd(K) is coNPhard. In fact, we show that it is complete for the class C=P and, hence, apparently much harder than coNP. We conclude our studies of HomInd(F) with a tractability result: HomInd(P) can be solved in polynomial time for the class P of directed paths. Finally, we briefly study some variants of HomInd(F). This is joint work with Yijia Chen, Martin Grohe, and Gaurav Rattan.

23/05/2019
13:00  14:00
The WeisfeilerLeman Dimension of Graphs of Bounded Treedepth
Luca Oeljeklaus
In this talk we discuss the dimension of the WeisfeilerLeman (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 WLdimension 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 (k1)dimensional WLalgorithm, we use the fact that the (k1)dimensional WLalgorithm identifying a graph is equivalent to Spoiler having a winning strategy for the C_kpebble game between a graph of treedepth at most k and any other nonisomorphic 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 WLalgorithm does not distinguish them, we apply the CFIgraph 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 DissociationsFloris GeertsSpeeding 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 #Phard, 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) MCMCstyle sampling or (ii) branchandbound (B&B) algorithms that iteratively improve modelbased 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 modelbased 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 modelbased algorithms. Here, in each iteration, a gradientdescent based optimization method finds the best scaled dissociation bounds after which Shannon expansion is performed. When applied to the wellstudied problem of evaluating selfjoinfree conjunctive queries over tupleindependent 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 twoparty games between computational agents. Double efficiency denotes the practice of limiting both parties to efficient computation. We present in detail the recently published, doublyefficient interactive clique counting protocol of Oded Goldreich and Guy N. Rothblum. Contrary to previous proof systems, that use the sumcheck 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 WeisfeilerLeman Dimension of Graphs of Bounded GenusSandra KieferThe WeisfeilerLeman (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 WeisfeilerLeman 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 firstorder logic with counting quantifiers.
It is known that the WL dimension is upperbounded 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 WLdimension of graphs of bounded rank widthDaniel NeuenWe prove that the combinatorial WeisfeilerLeman 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 nonelementary 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 fixedpoint 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

14/12/2018
10:00  11:00
ATI
Color Refinement and Graph Neural NetworksMartin RitzertIn this talk we show that the expressive power of the 1dimensional 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 NPSchwereBeweis für GD und ein κ^4Approximationsalgorithmus 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

30/11/2018
10:00  11:00
ATI
Universal graphs for parity and meanpayoff gamesNathanaël FijalkowI 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 meanpayoff 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 meanpayoff games * show tight lower bounds for the construction of algorithms in this framework for both parity and meanpayoff games

30/11/2018
10:00  11:00
ATI
Universal graphs for parity and meanpayoff gamesNathanaël FijalkowI 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 meanpayoff 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 meanpayoff games * show tight lower bounds for the construction of algorithms in this framework for both parity and meanpayoff games

23/11/2018
10:30  11:30
ATI
Detecting small subgraphs using the exterior algebraHolger DellColorcoding is a popular technique to detect and to approximately count short paths and other subgraphs of bounded treewidth. In this talk, we will discuss Extensorcoding, a natural approach to such subgraph detection problems that turns out to generalize and in some cases improve upon the running time achieved by Colorcoding. Based on joint work with Cornelius Brand and Thore Husfeldt.

16/11/2018
10:00  11:00
ATI
Structural Similarity and Homomorphism CountsJan 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 objectsDaniel WiebkingWe 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 SupervisionZeynep Akata (University of Amsterdam)Clearly explaining a rationale for a classification decision to an enduser 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 visionlanguage models can describe image content but fail to take into account classdiscriminative image properties which justify visual predictions. In this talk, I will present my past and current work on ZeroShot 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 functionsMikołaj BojańczykI will describe a class of stringtostring 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 stringtostring 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 forprograms; 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 stringtostring 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 FOsentence 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 twovariable logic and threevariable 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_1complete 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 NPcomplete. 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 worstcase 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 firstorder logic
Bianka Bakullari
The WeisfeilerLeman algorithm is a combinatorial procedure used to distinguish nonisomorphic graphs. I give an introduction to the mechanisms of the algorithm by putting the focus on the 2dimensional variant of it, for which I explain the nontrivial 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 WeisfeilerLeman 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 nonisomorphic finite relational structures.

28/09/2018
11:45  12:30
BSc
Parameterized Approximability of Dominating Set
Daniel Schleiz
Due to the NPhardness 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
Optimizationbased 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 [CohenAddad 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
Realvalued Connectivity Systems
Eva Fluck
Based on a survey on connectivity, decompositions and tangles by Grohe [5], we adapt the so far integervalued theory onto realvalued 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 integervalues, to do inductive arguments using a value called granularity, which is the smallest nonzero 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 wellknown tree decompositions, into this new setting. We are able to prove that both definitions behave similar to integervalued 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 nonexistence 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 realvalued connectivity systems into their maximal tangles.

26/09/2018
12:00  12:45
BSc
DistanceAware 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 twodimensional WeisfeilerLeman 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 multihypergraphs. 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 threecolorable 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 colorrefinement 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 colorrefinement algorithm for multihypergraphs and prove that it does not distinguish two multihypergraphs G and H if and only if, for every Bergeacyclic multihypergraph B, we have Hom(B, G) = Hom(B, H). To this end, we show how homomorphisms of multihypergraphs and their colored incidence graphs are related to each other.