Pascal Schweitzer (TU Darmstadt): Recent insights surrounding combinatorial approaches to isomorphism and symmetry problems
Abstract:
Modern practical software libraries that are designed for isomorphism tests and symmetry computation rely on combinatorial techniques combined with techniques from algorithmic group theory. The Weisfeiler-Leman algorithm is such a combinatorial technique. When taking a certain view from descriptive complexity theory, the algorithm is universal. After an introduction to problems arising in symmetry computation and this particular combinatorial technique, I will give an overview of results from recent years. The results give insights into worst-case behavior and computational complexity. In the course of this, I will discuss combinatorial “cops and robbers” games and some lower bound constructions.
Mit freundlichen Grüßen,
Prof. Dr. Torsten Mütze (AG AADM)