BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A super-linear lower bound for the iteration number of the Weisfei
 ler-Leman algorithm - Moritz Lichter (RWTH\, Aachen)
DTSTART:20250401T130000Z
DTEND:20250401T140000Z
UID:TALK229039@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:A super-linear lower bound for the iteration number of the Wei
 sfeiler-Leman algorithm\n\nThe k-dimensional Weisfeiler-Leman (k-WL) algor
 ithm is a simple combinatorial algorithm that was originally designed as a
  graph isomorphism heuristic. It naturally finds applications in Babai's q
 uasipolynomial-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 optimizat
 ion\, and machine learning.\n\nThe algorithm iteratively computes a colori
 ng of the k-tuples of vertices of a graph. Since Fürer's linear lower bou
 nd 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.\nThis talk answer
 s 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.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR