On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
Joshua A. Grochow and Michael Levet
在本文中,我们展示了用于群的常数维Weisfeiler-Leman算法(Brachter Schweitzer, LICS 2020)可以有效地用于改进多个群族同构测试的并行复杂性上界。具体来说,我们表明: - 具有阿贝尔正规Hall子群且其补群为O(1)-生成的群可以通过常数轮数的常数维Weisfeiler-Leman进行识别。这将此类群的同构测试置于;之前的同构测试上界为(Qiao, Sarma, Tang, STACS 2011)。 - 我们使用个体化-精化范式,通过深度O(log n)和大小n^O(loglog n)的电路获得无阿贝尔正规子群的群的同构测试,此前仅知属于(Babai, Codenotti, & Qiao, ICALP 2012)和𝗊𝗎𝖺𝗌𝗂𝖲𝖠𝖢^1(Chattopadhyay, Torán, & Wagner, ACM Trans. Comput. Theory, 2013)。 - 我们将Brachter & Schweitzer(ESA, 2022)关于群直积的结果扩展到并行设置。即,我们还表明Weisfeiler–Leman可以并行识别直积,前提是它能并行识别每个不可分解直因子。他们先前展示了类似的结果。 最后,我们考虑无计数Weisfeiler–Leman算法,其中我们表明无计数WL甚至无法在多项式时间内区分阿贝尔群。尽管如此,我们将无计数WL与有界非确定性和有限计数结合使用,获得了阿贝尔群同构测试的新上界β_1^0()。这改进了Chattopadhyay, Torán, & Wagner(同上)之前的^0()上界。
In this paper, we show that the constant-dimensional Weisfeiler-Leman algorithm for groups (Brachter Schweitzer, LICS 2020) can be fruitfully used to improve parallel complexity upper bounds on isomorphism testing for several families of groups. In particular, we show: - Groups with an Abelian normal Hall subgroup whose complement is O(1)-generated are identified by constant-dimensional Weisfeiler-Leman using only a constant number of rounds. This places isomorphism testing for this family of gr...