Welcome
Our group's interests in both research and teaching are in various areas within the theory of computation, among them logic, complexity theory, algorithms, and automata theory, and especially the numerous connections between these areas.
Computer Science 7 is part of the Computer Science Department within the Faculty of Mathematics, Computer Science and Natural Sciences. There is a close collaboration with the Mathematical Foundations of Computer Science group.
News
Wednesday, 26.09.2018
12:00

12:45
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.
Friday, 28.09.2018
11:00

11:45
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.
Friday, 28.09.2018
12:30

13:15
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.