3 papers
cs.DS2026
Isomorphism of tournaments with bounded VC dimension
Simon Raßmann, Pascal Schweitzer
The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investiga…
cs.LO2024
Finite Variable Counting Logics with Restricted Requantification
Simon Raßmann, Georg Schindling, Pascal Schweitzer
Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula…
cs.CC2024
Computational complexity of the Weisfeiler-Leman dimension
Moritz Lichter, Simon Raßmann, Pascal Schweitzer
The Weisfeiler-Leman dimension of a graph is the least number such that the -dimensional Weisfeiler-Leman algorithm distinguishes from every other non-isomorphic gra…