
Termin
Titel

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 RefinementSandra KieferThe Colour Refinement procedure and its generalisation to higher dimensions, the WeisfeilerLeman 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 n1. 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 G1 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 n2 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 DistributionsPeter LindnerProbabilistic 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 HypergraphsDaniel NeuenWe 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
RUNCSP: Recurrent unsupervised network for CSPsMartin RitzertConstraint 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 RUNCSP (Recurrent Unsupervised Neural Network for Constraint Satisfaction Problems) to train message passing networks solving binary constraint satisfaction problems (CSPs) or their optimization versions (MaxCSP). 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 3colorability problem (3Col) and its optimization version (Max3Col) and for the maximum 2satisfiability problem (Max2Sat). We also extend the framework to work for related optimization problems such as the maximum independent set problem (MaxIS). 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 10times larger).

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 objects Daniel 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.

14.09.2018
12:00  12:45
BSc
EndtoEnd Graph Learning
Emre Yamen
In der Präsentation wird EndtoEnd 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 WeisfeilerLeman subtree kernel eingegangen. Danach werden Experimente zur Graphen Klassifizerung mit EndtoEnd Graph Learning und Graph Kanonisierung in einem neuronalen Netzwerk vorgestellt. Das Ergebnis wird mit dem Ergebnis vom WeisfeilerLeman 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 NPcompleteness 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 NPhard, 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 NPhardness.

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 structuresPeter LindnerAutomatic structures are of particular interest, since their first order theories are decidable. While these theories might be of nonelementary complexity in general, the practically relevant examples are located below 3fold exponential time (e. g. Presburger arithmetic and automatic structures of bounded degree). It was an open question [DurandGasselin], 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 kEXPTIME 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 kequitable partitions to state the kdimensional colour refinement algorithm for weighted directed graphs. Thirdly, we generalise kequitable partitions and kdimensional 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 determinisationAnton PirogovNondeterministic 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 ProblemDaniel NeuenI 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 ConstraintsPatrick LandwehrWe 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 emptinessproblem.

04.05.2018
10:15  11:15
Lovasz meets Weisfeiler and LemanMartin GroheI 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 WeisfeilerLeman 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 LemanMartin GroheI 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 WeisfeilerLeman 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 isomorphisminvariant 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 isomorphisminvariant nested tree decompositions. Our second contribution is the collection and combination of existing algorithms to compute an algorithm that outputs an isomorphisminvariant nested tree decomposition of a given graph. The combination of this algorithm with our approach to testing isomorphism introduced above, which employs Babai's quasipolynomialtime 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
SMTbased 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 #Pcomplete. Polynomialtime algorithms for exact counting problems tend to be rare and curious, but even for the #Phard 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 exponentialtime 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 Hcopies 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

03.11.2017
10:15  11:15

27.10.2017
10:15  11:15
Uniformization Problems for Synchronizations of Relations on WordsSarah WinterA 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 IsomorphismGaurav RattanThe 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 wellstudied 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 NPhard even for severely restricted cases. It is known that SIM (WSIM) is NPhard: we strengthen this hardness result by showing that the problem remains NPhard 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 semidefinite, have boundedrank, 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 NPhardness for matrices of bounded rank and for positivesemidefinite 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 PolynomialTime Randomized Reduction from Tournament Isomorphism to Tournament AsymmetryPascal SchweitzerThe 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 polynomialtime 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 polynomialtime Turingreduction 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 polynomialtime 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 NPvollstä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 polynomialtime 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 4universal 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 4universal 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 2universal hashing, and a strongly 3universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4universal 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 NPvollstä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 polynomialtime 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 4universal 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 4universal 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 2universal hashing, and a strongly 3universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4universal 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 contextfree games
Michael Mutert
Bachelor Kolloquium

28.09.2017
11:00  12:00
A comparison of algorithms for games on pushdown automata and contextfree 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 LowenheimSkolem property
Abhisekh Sankaran
We present a modeltheoretic property of finite structures, that can be seen to be a finitary analogue of the wellstudied downward LowenheimSkolem 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 treedepth, those of bounded shrubdepth and mpartite cographs. Further, EBSP remains preserved in the classes generated from the above using various wellstudied operations, such as complementation, transpose, the linegraph 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 selfsimilarity 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 FOInterpretations
Dimitri Rusin

01.09.2017
10:00  11:00
FO Model Checking on some Dense Graph Classes using FOInterpretations
Dimitri Rusin

31.08.2017
12:00  12:30
Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TCLogiken
Yannic Rohde

31.08.2017
12:00  12:30
Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TCLogiken
Yannic Rohde

30.08.2017
11:00  12:00
Homomorphisms are a good basis for counting small subgraphsHolger DellWe introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constantsize induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of Hcopies (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 kedge matchings or O(n0.46k+c) time for kcycles. 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 vertexcolored graphs H and G, where H is from a fixed class H, we want to count colorpreserving Hcopies in G. We show that this problem is either polynomialtime 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 subgraphsHolger DellWe introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constantsize induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of Hcopies (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 kedge matchings or O(n0.46k+c) time for kcycles. 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 vertexcolored graphs H and G, where H is from a fixed class H, we want to count colorpreserving Hcopies in G. We show that this problem is either polynomialtime 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 Lcomplete) by Datta, Limaye, Nimbhorkar, Thierauf and Wagner. We generalize the decomposition technique used in their result to work with minorclosed graph classes whose 3connected members fulfill a fixability condition and admit a logspace canonization algorithm.

24.08.2017
10:30  10:30
WeisfeilerLehman 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 WeisfeilerLehman 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 stateoftheart 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 WeisfeilerLehman subtree kernel. Before we make these observations we provide brief introductions into WeisfeilerLehman 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 bottomup recursion upon these components. For this to work I introduce a generalization of the fixing number, the socalled vertexarc 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 minorclosed graph class that allows isomorphism testing and computing the vertexarc fixing number of its triconnected graphs in polynomial time.

28.07.2017
10:15  11:45
ATI
FixedParameter Tractable Canonization for Graphs of Bounded TreewidthDaniel 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 twoway 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 BeyondChristopher MorrisGraph kernels are a popular approach to graph comparison and at the heart of many machine learning applications in bioinformatics, imaging, and socialnetwork 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 WeisfeilerLehman 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 boundeddegree 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 algorithmsSpyros AngelopoulosStochastic 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 twofold. 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 kserver 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 TimeSpace Lower Bound for Parity Learning
work by Ran Raz

07.07.2017
11:15  12:15
Enumerating Tree Decompositions: Why and HowBenny KimelfeldMany 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 subproblems 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 highquality tree decompositions for the application to choose from. I will describe our application of tree decompositions in the context of “worstcase optimal” joins  a new breed of inmemory 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, coauthored with Nofar Carmeli, Yoav Etsion, Oren Kalinsky and Batya Kenig.

04.07.2017
16:00  17:00
The hardness of embedding grids and wallsYijia ChenThe 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 fixedparameter 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 degreeIsolde AdlerProperty 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 firstorder logic is testable with a constant number of queries in constant time. On structures of bounded treewidth, monadic secondorder 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 WeisfeilerLeman Dimension of Planar Graphs is at most 3Sandra KieferWe prove that the WeisfeilerLeman (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 WLalgorithm correctly tests isomorphism of graphs in a minorclosed class whenever it determines the orbits of the automorphism group of any vertex/arccolored 3connected graph belonging to this class. Then we prove that, apart from several exceptional graphs (which have WLdimension at most 2), the individualization of two correctly chosen vertices of a colored 3connected planar graph followed by the 1dimensional WLalgorithm produces the discrete vertex partition. This implies that the 3dimensional WLalgorithm determines the orbits of a colored 3connected planar graph. As a byproduct of the proof, we get a classification of the 3connected 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 ComputationErkal Selman

02.06.2017
10:15  11:45
ATI
A Purely Relational Language for Choiceless ComputationErkal 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

17.05.2017
15:30  16:30
Answering database queries under updatesNicole SchweikardtQuery 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 kary relation obtained by evaluating a kary query Q on a relational database D. For Boolean queries, all three tasks boil down to (4) Answering: Decide if Q(D) is nonempty. Compared to the dynamic descriptive complexity framework introduced by Patnaik and Immerman (1997), which focuses on the expressive power of firstorder 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

05.05.2017
10:15  11:45
ATI

28.04.2017
10:15  11:45
ATI
On the Expressiveness of Unfolding Proofs for Recursive Data StructuresChristof LödingUnfolding 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 UrbanaChampaign), 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 quasipolynomial time
Katrin Dannert
The problem of deciding parity games is known to be in NP and in coNP 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 MultiteamSemantik
Richard Wilke
Klassische Logiken werden mit der so genannten TarskiSemantik 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 TeamSemantik. 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 MultiteamSemantik, welche sich eben dieser Herausforderung stellen.

03.03.2017
10:15  11:15
The FirstOrder Logic of HyperpropertiesMartin ZimmermannWe 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 firstorder logic. Kamp's seminal theorem (in the formulation due to Gabbay et al.) states that lineartime temporal logic (LTL) is expressively equivalent to firstorder logic over the natural numbers with order. We introduce firstorder 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 FirstOrder Logic of HyperpropertiesMartin ZimmermannWe 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 firstorder logic. Kamp's seminal theorem (in the formulation due to Gabbay et al.) states that lineartime temporal logic (LTL) is expressively equivalent to firstorder logic over the natural numbers with order. We introduce firstorder 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 GIGaurav RattanUsing 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 IsomorphismDaniel NeuenThe 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 kdimensional Weisfeiler Leman is used for refinement instead of color refinement (i.e. 1dimensional 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 IsomorphismDaniel NeuenThe 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 kdimensional Weisfeiler Leman is used for refinement instead of color refinement (i.e. 1dimensional 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
NMemory Automata Over the Alphabet NPatrick LandwehrAn automaton model for words over the alphabet of the natural numbers is presented  the so called Nmemory automaton. We explain its close connection to MSOlogic and discuss its expressive power and closure properties. Additionally we show among other decidability results the solvability of the nonemptiness 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 FirstOrder 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 monomialPC (a weaker variant of the Polynomial Calculus) which are guaranteed to produce polynomialsize proofs. It turns out that the power of these restricted proof systems can be described in terms of other wellknown logics, namely we obtain equivalences with least fixedpoint logic (LFP), existential least fixedpoint logic (EFP) and fixedpoint logic with counting (FPC).