Pascal Schweitzer (TU Darmstadt): Recent insights surrounding combinatorial approaches to isomorphism and symmetry problems

@Institut für Mathematik

Livestream: https://uni-kassel.cloud.panopto.eu/Panopto/Pages/Sessions/List.aspx?folderID=d9242d60-5cb4-4afc-ac3d-adb700e7b246

 

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)

Verwandte Links