Talks (Archive)
Showing 1  50 of 199 Results

DateTitle

14/10/2021
15:00  16:00MScMasterKolloquium Zeno Bitter
Title: Weisfeiler–Leman Invariant Induced Subgraph Counts Speaker: Zeno Bitter Time and Place: Thursday, October 14, 15:00, seminar room of chair computer science 7 and on Zoom Please make sure you observe the current RWTH rules for tackling the Covid19 pandemic when attending the talk in person. You may only participate if you are vaccinated against, tested negative for or recovered from Covid19. https://rwth.zoom.us/j/98409488429?pwd=YkkycFR5S0N6TGRWeHBiR3FQVDNHUT09 Meeting ID: 984 0948 8429 Passcode: 396495 Abstract: The $k$dimensional Weisfeiler–Leman ($k$WL) algorithm is a strong graph invariant which sees wide use in both theoretical and practical algorithms for the Graph Isomorphism Problem (textbf{GI}), and in machine learning applications as a graph kernel. As $k$WL falls short deciding textbf{GI} for all $k$, it gives rise to a coarser equivalence relation on the class of all graphs based on indistinguishability. In this work we study invariant functions under these equivalence relations, with a focus on induced subgraph counts and small $kin{1,2}$. For the case of $k=1$ we obtain a complete description of the induced subgraphs whose counts are invariant, while for $k=2$ we obtain results for path, cycle and matching graphs. In both cases we match known results for noninduced subgraphs. 
12/10/2021
11:15  12:00BScThe Complexity of Homomorphism Indistinguishability
Duc Khuat
The foundation of Homomorphism Indistinguishability was laid by Lovász’ Theorem in 1966, stating that a graph is defined up to isomorphism by the number of homomorphism from all graphs to the studied graph and from the studied graphs to all other graphs, respectively. Collecting these numbers in an infinite vector, motivates the notion of homomorphism vectors. Now, as an infinite dimensional vector we define projections onto entries corresponding to a fixed subset of the set of all graphs. We call two graphs homomorphism indistinguishability over this subset if the projection image of the graphs are equal. Strong recent results characterize homomorphism indistinguishability over some natural classes such as the class of planar graphs, class of bounded tree depth and tree width, respectively with well studied notions, combining results of the past forty years with this single framework. In my thesis I provide an overview and a list of references, combining the ideas and the machineries used to establish the recent results but also well known results from the fields of logic, graph theory, combinatorics and quantum and game theory. A proper focus lies on the analysis of complexity of homomorphism indistinguishability. From the characterisations emerging complexity results will be explicated and extended by an algorithm deciding homomorphism in distinguishability over graphs of bounded tree depth in polynomial time and the fptintractability of first order logic of bounded quantifier rank equiva lence. 
12/10/2021
12:00  12:45BScLower Bounds for Learning Logical Concepts
Constantin Rettig
We study the complexity of learning concepts definable in firstorder or monadic secondorder logic for relational structures. We introduce a uniform notation for the framework, with which we will remove irregularities among related work. The main focus here lies on the lower bound on the running time for logic learning algorithms. We go over results for string structures, showing that for unary and binary FO formulas there is no consistent learning algorithm running in sublinear time in the size of the structure. For tree structures we show the same results and in addition see that the sublinear bound on logic learning holds for quantifier free formulas. It is shown that for structures with small degree the sublinear time bound holds for logic learning algorithms given local access. After that, we present a section over parameter learning, showing that parameter learning is not possible in sublinear time for structures of small degree. In addition, we show that the parameter learning problem on structures with no degree restrictions is as hard as solving the qCLIQUE problem on graphs. In the last section we show that concept learning (also in the Probably Approximately Correct (PAC) setting) is as hard as the firstorder modelchecking problem in the parametrised setting. In the conclusion we sum up the presented results and give a outlook on possible future work. 
07/10/2021
10:00  11:00BScGraph Neural Networks for MAXSAT
Mert Basaran[bachelor]
We present RUNSAT, a novelrecurrent message passing neural network. RUNSAT learns to approximate MAXSATin an unsupervised manner. The architecture can be applied to arbitrary CNFformulas. We experimentally evaluate our approach on the SAT and MAXSATproblems and compare the performance to conventional solvers, heuristics andother neural architectures.

23/09/2021
14:00  15:00Learning on graphs with logic and neural networks
Martin Ritzert
https://rwth.zoom.us/j/95250295111?pwd=cjhFMGk0bStZcGNvcmYrYURPWnQ0dz09 In the domain of graphs we show strong connections between logic and machine learning in both theory and practice. In a purely theoretical framework we develop sublinear machine learning algorithms for supervised learning of logical formulas on various graph classes. Further we show that learning firstorder logic on arbitrary graphs is intractable unless P=NP. At the intersection of theory and practice, we prove an equivalence between graph neural networks and the 1dimensional WeisfeilerLeman algorithm. As a practical application, we approximate combinatorial problems with recurrent graph neural networks. The proposed architecture is unsupervised and can be applied to all maximum constraint satisfaction problems. 
09/09/2021
11:00  11:30MScNondeterministic Deep Weisfeiler Leman
Louis Härtel
https://rwth.zoom.us/j/5419503919?pwd=enlnbm1mclNBNkVQZTgvVXR4RTRHZz09 
06/09/2021
14:00  15:00BScBachelorKolloquium Matthäus Micun
Counting and Sampling based on Nondeterministic Logspace Transducers Abstract: Transducers are Turing machines that, instead of deciding problems, compute witnesses. Additionally, nondeterministic Transducers compute relations of witnesses. In this paper, we discuss nondeterministic logspace transducers (NL transducers), as well as their unambiguous version (UL transducers). More specifically, we prove that for any relation computed by an NL transducer, we can enumerate the witnesses of a given word w with polynomial delay, count the number of all witnesses using a fully polynomial randomized approximation scheme (FPRAS), and uniformly generate a witness using a preprocessing polynomial time Las Vegas uniform generator (PPLVUG). Additionally, we connect these properties to nondeterministic finite automata, and prove that the #NFA problem admits an FPRAS. 
02/09/2021
15:00  16:00Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen
Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of wellstudied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set. 
02/09/2021
15:00  16:00Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen
Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of wellstudied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set. 
11/08/2021
15:00  15:30Facility Location and Clustering on Planar and Almost Planar Graphs
Sebastian Schaub
Masterkolloquium
ZoomMeeting beitreten
https://rwth.zoom.us/j/99375584947?pwd=UVNSaTBNRm1qL2ZneDExWVVZUUxKZz09
MeetingID: 993 7558 4947
Kenncode: 600407
Abstract: In this thesis we will reflect the current state of research for the uniform facility location problem and kClustering in terms of approximability. We will focus our attention on the special case of the planar graph metric, because for the problems with general metric no polynomialtime approximation scheme exist.
To illustrate this we will depict and explain four recent results which use different techniques for the analysis of the algorithms, including Voronoi Diagrams, rdivisions and coresets. The first result is an algorithm accuracy analysis for the uniform facility location, where we show that a commonly known local search algorithm is a polynomialtime approximation scheme. The second result is an efficient polynomialtime randomised approximation scheme, where we use an algorithm for the kMedian problem as a subroutine to derive a solution. For the third result we have another polynomialtime approximation scheme with a local search algorithm for the kClustering problems kMedian and kMeans. And the fourth result is a fully polynomialtime randomised approximation scheme for the kMedian problem, where the algorithm is based on constructing coresets. 
29/07/2021
11:00  12:00Simulation Relations for Symbolic Automata, Rober Funk, Masterkolloquium 
29/07/2021
11:00  12:00Simulation Relations for Symbolic Automata, Rober Funk, Masterkolloquium 
21/07/2021
10:00  11:00Learning and Minimization of omegaAutomata in the Presence of Don’t CareWords, Max Stachon
Masterkollquiumhttps://rwth.zoom.us/j/93883134873?pwd=Y1lKYXpEZHBlaHlmUWtHSG9VQ1M5Zz09

14/07/2021
10:00  12:00Tree Automata with Constraints on Infinite Trees
Patrick Landwehr 
06/07/2021
10:30  11:15Comparing Algorithms for Weak Parity Games, Jonas FörsterBachelorkolloquium
https://rwth.zoom.us/j/94010226440?pwd=VnNFZzczR0p1ZUxNY2lLQnU2SmUxdz09

28/06/2021
12:30  13:30BScThe Logical Expressiveness of Graph Neural Networks
Attila Lischka
https://rwth.zoom.us/j/95314638975?pwd=bForQjRoZXN1YlhRd29IQlFVQkNuQT09 
28/06/2021
12:30  13:30BScThe Logical Expressiveness of Graph Neural Networks
Attila Lischka
https://rwth.zoom.us/j/95314638975?pwd=bForQjRoZXN1YlhRd29IQlFVQkNuQT09 
14/06/2021
16:00  16:30A DecompositionCompatible Canonization Framework for the Graph Isomorphism Problem
Daniel Wiebking
https://rwth.zoom.us/j/94470149252?pwd=ZnYwVXQrbStveVdDNDk1V1BlN1lJUT09 
11/05/2021
15:00  15:30Bachelorkolloquium Martin Krüßel 
16/04/2021
14:00  14:30Bachelorkolloquium Jonas Groven 
22/03/2021
10:30  11:15Bachelorkolloquium Jonathan Schneider 
01/03/2021
10:00  10:45Bachelorvortrag Alexander Cushicondor
Title: "Homomorphism Indistinguishability over Structures of Bounded Tree Depth" Abstract: It will be proved that two structures G, G' satisfy the same sentences of quantier rank at most k of first order logic with counting, if and only if they are homomorphismindistinguishable over the class of structures of tree depth at most k. 
22/02/2021
10:00  10:30Nondeterministic Automata with XORacceptance
Jagadish Singh
https://rwth.zoom.us/j/94253016445?pwd=VVdScGUzOFNJamZ5MCtRclYwK2xDdz09 
18/02/2021
10:15  11:15Oberseminar Anton Pirogov: Determinization and Ambiguity of Classical and Probabilistic Büchi Automata
Anton Pirogov
Büchi automata can be seen as a straightforward generalization of
ordinary NFA,
adapted to handle infinite words. While they were originally introduced for
applications in decidability of logics, they became a popular tool for
practical
applications, e.g. in automatabased approaches to model checking and
synthesis
problems. Being arguably both the simplest and most wellknown variant
in the
zoo of socalled omegaautomata that are considered in this setting, they
serve as an intermediate representation of omegaregular specifications of
verification or synthesis requirements that are usually expressed in a more
declarative fashion, e.g. using linear temporal logic.
Unfortunately, nondeterministic automata are not directly suitable for
certain
applications, whereas deterministic Büchi automata are less expressive. This
problem is usually solved by either constructing deterministic automata of a
different kind, or by restricting their ambiguity, i.e., the maximal
number of
accepting runs on some word. In both cases, the transformation is expensive,
yielding an exponential blowup of the state space in the worst case.
Therefore,
optimized constructions and heuristics for common special cases are
useful and
in demand for actual practical applications.
In this talk we present a new general construction for determinization from
nondeterministic Büchi to deterministic parity automata that unifies the
dominant branches of previous approaches based on the Safra construction
and the
MullerSchupp construction. Additionally, we sketch a number of new
heuristics
for determinization, some of which exploit properties of our unified
construction.
Apart from the classical nondeterministic and deterministic variants of
automata, it is natural to consider probabilistic automata, i.e.,
automata that
use a probability distribution on the states instead of nondeterminism
to decide
which state to go to next. It is known that in general, such automata
are more
expressive than classical automata and many decision problems are
undecidable.
We present subclasses of probabilistic automata that correspond to certain
ambiguity classes and are not more expressive than classical automata. 
08/01/2021
10:00  11:00ATIDeep Weisfeiler Leman
Daniel Wiebking
We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the wellknown WeisfeilerLeman algorithm.
We prove that, as an abstract computational model, polynomialtime DeepWLalgorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic., 1999).
It is a wellknown open question whether the existence of a polynomialtime graph isomorphism test implies the existence of a polynomialtime canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomialtime DeepWL isomorphism test, then there is a polynomialtime canonisation algorithm for this class. This implies that there is also a logic capturing polynomial time on this class. 
18/12/2020
10:30  11:00BachelorVortrag: The Logical Structure of Probabilistic Databases
Jonas Lindner
As probabilistic databases (PDBs) may be very large, compact representation systems for these frameworks have been studied. But because complete representation systems (like pctables) can lead to very complex probability spaces, considering simpler and more intuitive noncomplete representation systems, e.g. TItables or BIDtables, is of interest. These fundamental ’building blocks’ are especially interesting as they can be extended with views from the relational calculus to be more expressive. Similar to work done by Das Sarma et al. on representation systems for incomplete databases, this thesis introduces logical properties in order to separate the classes of PDBs that are representable with noncomplete representation systems. The properties studied take a PDB’s underlying incomplete database as well as its probability distribu tion into account and therefore help to grasp its logical structure. Having conducted this examination, convex combinations of probabilistic databases are studied, as they offer some advantages over the commonly considered representation systems regarding expressiveness. 
12/11/2020
11:00  11:30Connectivity and Routing using Graph Neural Networks
Frorian Frantzen
Graph Neural Networks form a deep learning architecture for machine learning tasks on graphs. Recently, they have been used to obtain heuristics for hard combinatorial problems such as TSP, SAT, or constraint satisfaction problems. The purpose of this thesis is to investigate how such approaches perform on computationally much easier shortest path problems. We will present lower bounds regarding the depth and width of a message passing neural network, which must be fulfilled for such a model to learn the shortest path problem. Then we will evaluate an existing neural network  originally designed for the traveling salesperson problem  for its applicability to the shortest path problem. While this network will fail with insignificant accuracies, these tests will allow us to derive unique challenges of the shortest path problem and which weaknesses in the architecture we need to fix to achieve better results. Based on these results, we will built our own neural network architecture and train it both supervised and unsupervised. We will evaluate this network in terms accuracy, scalability to larger graphs and how well the network generalizes the shortest path problem. 
30/10/2020
10:00  11:00ATIFlag Algebras in Graph Theory
Tim Seppelt
Flag algebras as introduced by Razborov represent a powerful tool in extremal combinatorics. This talk will provide a gentle introduction to the framework highlighting applications graph theory. Moreover, limitations of flag algebraic techniques are discussed following the work of Hatami and Norine. 
30/10/2020
10:00  11:00ATIFlag Algebras in Graph Theory
Tim Seppelt
Flag algebras as introduced by Razborov represent a powerful tool in extremal combinatorics. This talk will provide a gentle introduction to the framework highlighting applications graph theory. Moreover, limitations of flag algebraic techniques are discussed following the work of Hatami and Norine. 
27/10/2020
14:00  14:30BScThe FineGrained Complexity of Longest Common Subsequence
Benjamin Stutte
[bachelor]We will examine approaches to finegrained analyses of the Longest Common Subsequence (LCS) problem with special attention to recent results that have proven lower bounds for solving LCS under the Strong Exponential Time Hypothesis. We will first showcase two results, one by Abboud et al. (FOCS’15) and the other by Bringmann et al. (FOCS’15), where subquadratic lower bounds have been proven for the general LCS problem. Later, we turn to Bringmann et al.’s (SODA’18) which examined the optimal running time of multivariate LCS which proved lower bounds that coincide with the running times of the fastest known algorithms. 
27/10/2020
14:45  15:15BScStable and Efficient Algorithms for Logarithmically Counting Homomorphisms from Selected Graph Classes
Anton Florey
Graph homomorphisms are mappings between two graphs H and G that preserve all edge relationsof the lefthand side graph. The graph homomorphism counting problem #Hom(H, G) asks for
the number of homomorphisms from one graph H ∈ H to another graph G ∈ G. It is polynomial
time solvable for certain lefthand graph classes H. As part of his recent master thesis, Maximilian
Merz already provided implementations of various homomorphism counting algorithms. Unfor
tunately, they quickly get impracticable for large problem instances, as homomorphism numbers
grow extremely fast. This work revisits most of these algorithms with the novel idea of counting
the logarithm of these numbers. One main contribution is the implementation and evaluation of
these adapted algorithms. For most of the newly implemented functions, a significant improve
ment in efficiency over the exact counting implementations can be measured. Further experiments
also show that errors of this logarithmic approximation stay sufficiently close to the unavoidable
accuracy loss induced by finite machine precision.
https://rwth.zoom.us/j/95988725888?pwd=NUlaM05VdU5Kdkp0NXVTZHplWlFSQT09 
27/10/2020
14:00  14:30BScThe FineGrained Complexity of Longest Common Subsequence
Benjamin Stutte
[bachelor]We will examine approaches to finegrained analyses of the Longest Common Subsequence (LCS) problem with special attention to recent results that have proven lower bounds for solving LCS under the Strong Exponential Time Hypothesis. We will first showcase two results, one by Abboud et al. (FOCS’15) and the other by Bringmann et al. (FOCS’15), where subquadratic lower bounds have been proven for the general LCS problem. Later, we turn to Bringmann et al.’s (SODA’18) which examined the optimal running time of multivariate LCS which proved lower bounds that coincide with the running times of the fastest known algorithms. 
27/10/2020
14:45  15:15BScStable and Efficient Algorithms for Logarithmically Counting Homomorphisms from Selected Graph Classes
Anton Florey
Graph homomorphisms are mappings between two graphs H and G that preserve all edge relationsof the lefthand side graph. The graph homomorphism counting problem #Hom(H, G) asks for
the number of homomorphisms from one graph H ∈ H to another graph G ∈ G. It is polynomial
time solvable for certain lefthand graph classes H. As part of his recent master thesis, Maximilian
Merz already provided implementations of various homomorphism counting algorithms. Unfor
tunately, they quickly get impracticable for large problem instances, as homomorphism numbers
grow extremely fast. This work revisits most of these algorithms with the novel idea of counting
the logarithm of these numbers. One main contribution is the implementation and evaluation of
these adapted algorithms. For most of the newly implemented functions, a significant improve
ment in efficiency over the exact counting implementations can be measured. Further experiments
also show that errors of this logarithmic approximation stay sufficiently close to the unavoidable
accuracy loss induced by finite machine precision.
https://rwth.zoom.us/j/95988725888?pwd=NUlaM05VdU5Kdkp0NXVTZHplWlFSQT09 
23/10/2020
10:30  11:00MScDetecting Substructures with Graph Neural Networks
Michael Scholkemper
[master]We present theoretical results relating the computational expressiveness of graph neural networks (GNNs) to the color refinement algorithm for graph isomorphism (Morris et al., X et al.). These yield that given the wrong initialisation, graph neural networks are not able to detect triangles on regular graphs. We introduce a refinement algorithm for graph isomorphism that outperforms color refinement on regular graphs and propose a GNNarchitecture motivated by this new algorithm. We experimentally investigate the effect of different initialisations on the detection of triangles and extend this to kcycles and kcliques. 
16/10/2020
10:00  11:00ATILearning Concepts Described by Weight Aggregation Logic
Steffen van Bergerem
We consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure. We introduce an extension of firstorder logic that allows to aggregate weights of tuples, compare such aggregates, and use them to build more complex formulas. We provide locality properties of fragments of this logic including FefermanVaught decompositions and a Gaifman normal form for a fragment called FOW1, as well as a localisation theorem for a larger fragment called FOWA1. This fragment can express concepts from various machine learning scenarios. Using the locality properties, we show that concepts definable in FOWA1 over a weighted background structure of at most polylogarithmic degree are agnostically PAClearnable in polylogarithmic time after pseudolinear time preprocessing. This is joint work with Nicole Schweikardt. 
13/10/2020
10:00  10:30BScA comparison of translation from LTL to Büchi automata
Anna Maiworm 
01/10/2020
10:00  10:45Bachelor Vortrag JanChristoph Kassing
Vortrag zur Bachelorarbeit: The Recursive Algorithm for Parity Games 
01/10/2020
10:00  10:45Bachelor Vortrag JanChristoph Kassing
Vortrag zur Bachelorarbeit: The Recursive Algorithm for Parity Games 
29/09/2020
10:00  10:45BachelorVortrag Johannes Lehmann
Vortrag zur Bachelorarbeit "Exact Minimization of omegaAutomata" 
29/09/2020
10:00  10:45BachelorVortrag Johannes Lehmann
Vortrag zur Bachelorarbeit "Exact Minimization of omegaAutomata" 
25/09/2020
10:30  11:00MScMasterVortrag: Graph Autoencoder for Chemical Compounds
Stefanie Winkler
https://rwth.zoom.us/j/91919735145?pwd=OWFJMDZ5aTErUjhLWEN0T1AwY0lIdz09 A challenging task in fuel design is to find suitable molecules that optimise desired properties like cetane and octane numbers. Our goal is to automate the generation of molecular graphs whose corresponding molecules serve as components for fuels with a high autoignition quality. We use three different neural network models built on variational autoencoders and a generative adversarial network: JTVAE by Jin et al., MHGVAE by Kajino and MolGAN by De Cao and Kipf [1–3]. Using a subset of QM9 for training, we adapt the models to optimise different combinations of the cetane and octane numbers of new molecules through Bayesian optimisation. Our results show that all models are able to produce valid molecules with high cetane and octane numbers. MHGVAE is able to generate most of the highest scoring molecules in the different experiments. Moreover, it creates a lot more unique molecules than the other two models, many of which are easy to synthesise. 
25/09/2020
11:15  12:00BScLower Bounds for the WeisfeilerLeman Dimension of Graphs of Bounded Tree Width
Lea Schirp
The WeisfeilerLeman (WL) algorithm is an iterative approach used to classify graphs and other relational structures. For every natural number k, there is a kdimensional version, which colors ktuples of vertices, running in polynomial time but there are also nonisomorphic graphs, which the kdim version cannot distinguish. This makes it useful to know the WLdimension of a graph, which is the least natural number k such that the kdim WL distinguishes the graph from all other nonisomorphic graphs. It is known that bounds on the WL dimension of a graph can be determined if its tree width is known. In this talk, we present tools for computing the tree width of a graph with a focus on Tamaki's implementation. We finally discuss the results of an experimental evaluation of the tree width of these graphs with the goal of finding out if the currently best known bounds on the WL dimension of graphs parametrized by their tree width are tight. 
25/09/2020
12:30  13:00BScCounting Homomorphisms via Model Counting and Knowledge Compilation
Patrick Bögel
The homomorphism counting problem #HOM asks how many homomorphisms there are from a graph H to a graph G. The model counting problem #SAT asks how many satisfying assignments a propositional formula has. Both problems are #Pcomplete, but #HOM becomes tractable if the lefthand side graphs are restricted to a class of bounded treewidth. In this talk we consider reductions from #HOM to #SAT with special attention to whether the tractable subproblems of #HOM are mapped to tractable subproblems of #SAT. Specifically we find reductions that map homomorphism counting instances where the lefthand side graph is a tree, to formulas which adhere to structural restrictions under which #SAT becomes tractable. We also utilize the approach of knowledge compilation to create formulas in a representation that allows for the model count to be calculated in linear time of its size. We evaluate the reductions practically with multiple stateoftheart model counters and find the reduction to be inferior to the direct approach. 
18/09/2020
10:00  11:00ATITupleIndependent Representations of Probabilistic Databases
Christoph Standke
https://rwth.zoom.us/j/96525649453?pwd=bHRma0lmV2xuRTNhWUdQbi9ockdNZz09 
03/08/2020
12:00  12:30BScBachelor Kolloquium Meder 
28/07/2020
16:00  17:00Vortrag Wolfgang Gatterbauer 
28/07/2020
16:00  17:00Vortrag Wolfgang Gatterbauer 
26/06/2020
10:00  11:00ATIATI Seminar Jan Böker
Jan Böker 
19/06/2020
10:00  10:45ATIATI Seminar Vortrag Steffen van Bergerem
Steffen van Bergerem 
05/06/2020
10:00  11:00ATIomegaWord Automata with Global Constraints
Patrick Landwehr