BARC talk by Daniel Neuen

Thursday, 14 November 2019, Daniel Neuen, PhD student at the RWTH Aachen University, Germany, will give a talk on "Faster Isomorphism Tests for Graphs of Bounded Degree and Beyond".

Title:
Faster Isomorphism Tests for Graphs of Bounded Degree and Beyond


Abstract:
In a recent breakthrough, Babai (STOC 2016) gave a quasipolynomial graph isomorphism test adding several novel techniques to the theory of the Graph Isomorphism Problem. In this talk, we focus on the group theoretic advances and extend the Local Certificates Routine, the key group-theoretic method ob Babai's algorithm, in several directions. As a result, we obtain, for example, an improved isomorphism test for graphs of maximum degree d running in time n^{polylog(d)} which significantly improves over the previous best algorithm running in time n^{O(d / log d)}. Also, the extensions of the Local Certificates Routine lay the foundation for possibly applying Babai's methods in a wider context, for example for the design of faster isomorhism tests for other important graph classes such as classes of bounded genus, bounded tree-width and more generally, classes that exlud a fixed graph as a minor.

Bio:
In September 2015 Daniel Neuen obtained his Master's degree in computer science at the RWTH Aachen University in Germany. Since November 2015 Daniel has been a PhD student supervised by Prof. Martin Grohe at the Logic and Theory of Discrete Systems group at RWTH Aachen University. His research lies in the area of algorithms and complexity. More precisely, he currently focuses on the theory of the Graph Isomorphism Problem and its various connections for example to computational group theory and logic.