Martin Grohe
The Graph Isomorphism Problem
VCLA and FWF-funded LogiCS hosted a talk by Martin Grohe
| DATE: | Monday, November 5, 2018 |
| TIME: | 16:00 c.t. |
| VENUE: | EI 4 Reithoffer lecture room, Gußhausstraße 25 (old building), 2nd floor |
ABSTRACT
The question of whether there is a polynomial time algorithm deciding if two graphs are isomorphic has been a one of the best known open problems in theoretical computer science for more than forty years. Indeed, the graph isomorphism problem is one of the very few natural problems in NP that is neither known to be in P nor known to be NP-complete. Three years ago, Babai (STOC 2016) gave a quasipolynomial time isomorphism algorithm. Despite of this breakthrough result, the question for a polynomial algorithm remains wide open. The first part of Martin Grohe´s talk will be a survey on the isomorphism problem. In the second part of the talk, he will speak about recent progress, starting from Babai's result and moving on to a new improvement for graphs of small maximum degree (G., Neuen, Schweitzer, FOCS 2018).
CONTACT
FWF-funded Doctoral College Logical Methods in Computer Science (LogiCS) and the Vienna Center for Logic and Algorithms (VCLA).
 Martin Grohe, RWTH AACHEN |
 The deputy speaker of the LogiCS Stefan Szeider introducing Martin Grohe. |
Martin Grohe
Martin Grohe studied mathematics in Freiburg, received his doctorate there in 1994 and returned to Freiburg after research stays at the University of California at Santa Cruz and at Stanford University. Martin Grohe has already shaped his field of research, finite model theory. Thus, in his dissertation he completely solved the so-called hierarchy problem for fixed-point logics, in which over a decade only fragmentary insights had been achieved.
Since the early 1980s, theoretic investigation of the problem of isomorphism has focused on group theoretical methods. One of the current Grohe´s projects funded by the German Research Foundation (DFG): Logik, Struktur und das Graphenisomorphie, uses techniques of modern graph structure theory as well as techniques of logic, more precisely finite model theory, which are known to be closely related to combinatorial approaches to solving the problem of isomorphism.
Venue
EI 4, Reithoffer lecture room, Gußhausstraße 25 (old building), 1040 Vienna.
The venue of the talk is the lecture room located on the second floor of the old building just next to the new building of TU Wien at Gußhausstraße 25.
