An Upper Bound on the Weisfeiler-Leman Dimension

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

• Pascal Schweitzer (TU Darmstadt)
• Wednesday 23 July 2025, 11:00-12:00
• Computer Laboratory, William Gates Building, Room GS15.

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

The Weisfeiler-Leman (WL) algorithms form a family of incomplete approaches to the graph isomorphism problem. They recently found various applications in algorithmic group theory and machine learning. In fact, the algorithms form a parameterized family: for each k ∈ ℕ there is a corresponding k-dimensional algorithm WLk. The algorithms become increasingly powerful with increasing dimension, but at the same time the running time increases. The WL-dimension of a graph G is the smallest k ∈ ℕ for which WLk correctly decides isomorphism between G and every other graph. In some sense, the WL-dimension measures how difficult it is to test isomorphism of one graph to others using a fairly general class of combinatorial algorithms. Nowadays, it is a standard measure in descriptive complexity theory for the structural complexity of a graph. We prove that the WL-dimension of a graph on n vertices is at most 3/20 ⋅ n o(n) = 0.15 ⋅ n o(n). Reducing the question to coherent configurations, the proof develops various techniques to analyze their structure. This includes sufficient conditions under which a fiber can be restored uniquely up to isomorphism if it is removed, a recursive proof exploiting a degree reduction and treewidth bounds, as well as an exhaustive analysis of interspaces involving small fibers. As a base case, we also analyze the dimension of coherent configurations with small fiber size and thereby graphs with small color class size.

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 GS15
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk449

Note that ex-directory lists are not shown.