[Proof Complexity] MIAO seminar Tue Apr 23 at 14:00 CE(S)T with Daniel Neuen: Compressing CFI graphs and lower bounds for Weisfeiler-Leman refinements

[Jakob Nordström]

Dear all,

On Tuesday April 23 at 14:00 CE(S)T we will have the pleasure of listening to Daniel Neuen from Universität Bremen, who will give a talk titled "Compressing CFI graphs and lower bounds for Weisfeiler-Leman refinements". You find the abstract at the bottom of this message.

This will be a video seminar at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at https://jakobnordstrom.se/miao-seminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Tuesday Apr 23 at 14:00 on Zoom
Compressing CFI graphs and lower bounds for Weisfeiler-Leman refinements
(Daniel Neuen, Universität Bremen)

The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai's quasipolynomial time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning.

The algorithm iteratively computes a coloring of the k-tuples of vertices of a graph. Since Fürer's linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for k-WL on graphs. In this talk, I present a novel method of compressing CFI graphs that leads to an Ω(n^{k/2}) lower bound for all k.

Joint work with Martin Grohe, Moritz Lichter and Pascal Schweitzer (published at FOCS 2023).


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se