Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, February 1, 2016

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room: Humboldt-Kabinett



Lecture - 14:15

Dietrich Kuske - Technische Universität Ilmenau

Hamiltonian paths and similar problems for automatic graphs

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

Christoph Berkholz - Humboldt-Universität zu Berlin

How not to solve graph isomorphism

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.



Letzte Aktualisierung: 21.01.2016