Sandra Kiefer

"The Power of Counting for Graph Comparison"

The graph isomorphism problem is one of the most fundamental computational problems whose complexity is still open. All competitive approaches to the problem make use of the Weisfeiler—Leman algorithm, which works by computing, counting, and comparing colour occurrences in the graphs.
The algorithm has links to numerous areas in computer science and beyond, thus insights about it often combine various perspectives and can have far-reaching impact. Still, even after decades of research and despite its simplicity, we lack a precise understanding of its expressiveness.
In my talk, I will shed light on the power of the algorithm to detect graph structure. I will analyse its two central parameters, the dimension and the number of iterations, in the context of related areas such as machine learning and logic. These connections yield new proof techniques, as I will illustrate throughout the talk.

Termin als Datei downloaden und in den Kalender importieren.