Martin Grohe

The Graph Isomorphism Problem

VCLA and FWF-funded LogiCS hosting 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), 1040 Vienna

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).

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. (Source German Research Foundation (DFG)) /

 / Since the early 1980s, theoretic investigation of the problem of isomorphism has focused on group theoretical methods. On the other hand, 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 called EI 4, located in the 4th floor of the old building just next to the new bulding of TU Wien at Gußhausstraße.

Map

 

Comments are closed.