BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:An Upper Bound on the Weisfeiler-Leman Dimension - Pascal Schweitz
 er (TU Darmstadt)
DTSTART:20250723T100000Z
DTEND:20250723T110000Z
UID:TALK234748@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:The Weisfeiler-Leman (WL) algorithms form a family of incomple
 te\napproaches to the graph isomorphism problem. They recently found vario
 us\napplications in algorithmic group theory and machine learning. In fact
 \,\nthe algorithms form a parameterized family: for each k ∈ ℕ there i
 s a\ncorresponding k-dimensional algorithm WLk. The algorithms become\ninc
 reasingly powerful with increasing dimension\, but at the same time\nthe r
 unning time increases. The WL-dimension of a graph G is the\nsmallest k 
 ∈ ℕ for which WLk correctly decides isomorphism between G and\nevery o
 ther graph. In some sense\, the WL-dimension measures how\ndifficult it is
  to test isomorphism of one graph to others using a\nfairly general class 
 of combinatorial algorithms. Nowadays\, it is a\nstandard measure in descr
 iptive complexity theory for the structural\ncomplexity of a graph.\nWe pr
 ove that the WL-dimension of a graph on n vertices is at most 3/20\n⋅ n 
 + o(n) = 0.15 ⋅ n + o(n).\nReducing the question to coherent configurati
 ons\, the proof develops\nvarious techniques to analyze their structure. T
 his includes sufficient\nconditions under which a fiber can be restored un
 iquely up to\nisomorphism if it is removed\, a recursive proof exploiting 
 a degree\nreduction and treewidth bounds\, as well as an exhaustive analys
 is of\ninterspaces involving small fibers.\nAs a base case\, we also analy
 ze the dimension of coherent configurations\nwith small fiber size and the
 reby graphs with small color class size.
LOCATION:Computer Laboratory\, William Gates Building\, Room GS15
END:VEVENT
END:VCALENDAR