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
Friday, 25.05.2018
10:15

11:15
Semin ar room i7
I 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.