A super-linear lower bound for the iteration number of the Weisfeiler-Leman algorithm

Add to your list(s) Download to your calendar using vCal

• Moritz Lichter (RWTH, Aachen)
• Tuesday 01 April 2025, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

A super-linear lower bound for the iteration number of the Weisfeiler-Leman algorithm

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 in 2001, it has been an open question whether there is a super-linear lower bound for the iteration number for k-WL on graphs. This talk answers this question, establishing an $\Omega(n^{k/2})$-lower bound for all $k$. The bound is based on a new compression technique of the so-called Cai-Fürer-Immerman graphs.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.