Monday, February 1, 2016
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room: Humboldt-Kabinett
Lecture - 14:15
Abstract:
Automatic graphs are (typically infinite) graphs that enjoy a finite
description by automata. Hence they form particular recursive graphs
where Turing machines (or arbitrary algorithms) are used instead of
automata.
We ask what properties of an automatic graph can be read of from the
automata describing it. We show the following:
- some natural problems (e.g., the existence of an infinite clique)
can be deduced "easily" from the automata.
- some natural problems (e.g., the existence of a Hamiltonian path)
are $\Sigma_1^1$-complete, i.e., they cannot be "conveniently"
deduced from the automata.
- some natural problems (e.g., the existence of an Eulerian path)
cannot be deduced "easily" from the automata, but they nevertheless
behave somewhat better than for recursive graphs.
Colloquium - 16:00
Abstract:
The graph isomorphism problem plays a prominent role in theoretical
computer science as it is one of the few natural problems in NP that are
neither known to be NP-complete nor in polynomial time.
One approach to find a polynomial time algorithm would be to apply
generic algorithmic tools.
This talk gives an overview on recent work establishing the limitations
of different methods.
In particular, linear and semi-definite optimization, SAT solver, and
algebraic solver based on Gröbner basis computations do not help to
solve graph isomorphism in polynomial time.