BARC/EADS Talk by Holger Dell

Titel

Lovász Meets Weisfeiler and Leman

Abstract

Lovász' beautiful theory about graph homomorphisms and graph limits has recently found several intriguing algorithmic applications. In this talk, Holger will in particular focus on its surprising connection with a popular heuristic for the graph isomorphism problem, known as the Weisfeiler-Leman algorithm. He also relate these notions to graph kernels in machine learning. The context of this is to design and understand similarity measures for graphs and other discrete structures.

Joint work with Martin Grohe and Gaurav Rattan.

Bio

Holger Dell is the head of the research group "Foundations of Exact Algorithms" at Saarland University and at the Cluster of Excellence (MMCI). He is interested in fast algorithms for hard problems, lower bounds, and counting complexity. In 2013-14, he was a postdoc at LIAFA (Université Paris Diderot), and in 2011-2013, he was a postdoc at the University of Wisconsin–Madison and a Feodor Lynen research fellow of the Humboldt Foundation. He obtained his PhD from the Humboldt University of Berlin in 2011 under the supervision of Martin Grohe. In 2007, he obtained his MSc from Saarland University.