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.08.2017
15:00

16:00
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.