Count-free Weisfeiler-Leman and group isomorphism (Q6545240)

The authors investigate the significance of counting in group isomorphism. They begin by utilizing the count-free variant of the Weisfeiler-Leman version I algorithm for groups [\textit{J. Brachter} and \textit{P. Schweitzer}, in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 287--300 (2020; Zbl 1498.20002)], combined with bounded non-determinism and limited counting, to enhance the parallel complexity of isomorphism testing for several families of groups. They demonstrate that the \(q\)-ary count-free pebble game fails to distinguish even abelian groups.