26/06/2020
10:00 - 11:00

ATI

ATI Seminar Jan Böker
Jan Böker

19/06/2020
10:00 - 10:45

ATI

ATI Seminar Vortrag Steffen van Bergerem
Steffen van Bergerem

05/06/2020
10:00 - 11:00

ATI

29/05/2020
10:00 - 10:30

ATI

Graph isomorphism in quasipolynomial time parameterized by treewidth
Daniel Wiebking

22/05/2020
10:00 - 11:00

ATI

The Iteration Number of Colour Refinement
Sandra Kiefer
The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n-1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G|-1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n ≥ 10, there are graphs on n vertices on which Colour Refinement requires at least n-2 iterations to reach stabilisation. This is joint work with Brendan McKay.

27/02/2020
10:00 - 10:30

MSc

Unsupervised machine learning for constraint satisfaction problems
Jan Tönshoff

27/02/2020
10:00 - 10:30

MSc

Unsupervised machine learning for constraint satisfaction problems
Jan Tönshoff

17/01/2020
10:00 - 11:00

ATI

Generative Datalog with Continuous Distributions
Peter Lindner
Probabilistic Databases (PDBs) are a formal model of uncertainty in relational databases, as might occur in a variety of practical application scenarios such as noisy or unreliable input data, data integration or data cleaning. Quite recently, Bárány et al. (TODS 2017) proposed a language called "Probabilistic Programming Datalog (PPDL)" which uses classic Datalog rules that are extended by random sampling. In a nutshell, PPDL is a declarative probabilistic programming language with very close ties to database applications and can be seen as a tool to specify PDBs. In this talk, we focus on the generative part of the language, "Generative Datalog". While the original language of Bárány et al. only supported discrete probability distributions, we allow using probability density functions and inputs that are already PDBs themselves. We present the formal semantics of the language and discuss various properties and consequences, most notably, the support of PDB inputs and robustness with respect to the order of rule applications. This is joint work with M. Grohe, B. L. Kaminski, J.-P. Katoen.

15/01/2020
10:00 - 10:30

MSc

Algorithms for counting homomorphisms from small treewidth graphs
Maximilian Merz

10/01/2020
10:00 - 11:00

ATI

Isomorphism Testing: From Strings to Hypergraphs
Daniel Neuen

We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices $V$ and a permutation group $Gamma$ over domain $V$, and asking whether there is a permutation $gamma in Gamma$ that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on $d$ points, this problem can be solved in time $(n+m)^{O((log d)^{c})}$ for some absolute constant $c$ where $n$ denotes the number of vertices and $m$ the number of hyperedges. The previous best algorithm for this problem due to Schweitzer and Wiebking (STOC 2019) runs in time $n^{O(d)}m^{O(1)}$.
 
As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding $K_{3,h}$ ($h geq 3$) as a minor in time $n^{O((log h)^{c})}$. In particular, this gives an isomorphism test for graphs of Euler genus at most $g$ running in time $n^{O((log g)^{c})}$.

13/12/2019
10:00 - 11:00

ATI

RUN-CSP: Recurrent unsupervised network for CSPs
Martin Ritzert

Constraint satisfaction problems form an important and wide class of combinatorial search and optimization problems with many applications in AI and other areas. We introduce a recurrent neural network architecture RUN-CSP (Recurrent Unsupervised Neural Network for Constraint Satisfaction Problems) to train message passing networks solving binary constraint satisfaction problems (CSPs) or their optimization versions (Max-CSP). The architecture is universal in the sense that it works for all binary CSPs: depending on the constraint language, we can automatically design a loss function, which is then used to train generic neural nets. In this paper, we experimentally evaluate our approach for the 3-colorability problem (3-Col) and its optimization version (Max-3-Col) and for the maximum 2-satisfiability problem (Max-2-Sat). We also extend the framework to work for related optimization problems such as the maximum independent set problem (Max-IS). Training is unsupervised, we train the network on arbitrary (unlabeled) instances of the problems. Moreover, we experimentally show that it suffices to train on relatively small instances; the resulting message passing network will perform well on much larger instances (at least 10-times larger).

29/11/2019
10:00 - 11:00

ATI

29/11/2019
10:00 - 11:00

ATI

22/11/2019
10:00 - 11:00

ATI

Ambiguity in Probabilistic Büchi Automata
Anton Pirogov
Probabilistic Büchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth 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 Fine-Grained Complexity of First-Order Properties
Louis Härtel
Based on the results by Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova and Ryan Williams, we break down the fine-grained complexity of first-order properties by analyzing their reduction from any model-checking problem on a (k + 1)-quantifier first-order formula to the sparse version of k-Orthogonal Vectors, and summarize their algorithmic improvements and consequences for common fine-grained conjectures.

15/11/2019
10:00 - 11:00

ATI

25/10/2019
10:00 - 11:00

ATI

Tree automata with global constraints for infinite trees
Patrick Landwehr
We 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 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.

14/06/2019
10:00 - 10: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). 

31/05/2019
10:00 - 11:00

ATI

The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
Daniel Neuen

The Weisfeiler-Leman procedure is a widely-used approach for graph
isomorphism testing, which iteratively computes an isomorphism-invariant
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 2-dimensional Weisfeiler-Leman 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 k-dimensional algorithm distinguishes
k-separators, i.e., k-tuples of vertices that separate the graph, from
other vertex k-tuples. 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 Weisfeiler-Leman 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 Weisfeiler-Leman Algorithm to Decompose Graphs
Daniel Neuen

The Weisfeiler-Leman procedure is a widely-used approach for graph
isomorphism testing, which iteratively computes an isomorphism-invariant
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 2-dimensional Weisfeiler-Leman 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 k-dimensional algorithm distinguishes
k-separators, i.e., k-tuples of vertices that separate the graph, from
other vertex k-tuples. 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 Weisfeiler-Leman 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 Indistinguishability
Jan Böker
We 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 polynomial-time 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 coNP-hard. 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 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

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

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

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³.