Faster Isomorphism for ?-Groups of Class 2 and Exponent ?
Faster Isomorphism for ?-Groups of Class 2 and Exponent ?
复制标题
2 类和指数的 ?-群的更快同构？
DOI：
10.1145/3564246.3585250
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Sun, Xiaorui
中科院分区：
文献类型：
--
作者：
Sun, Xiaorui
群同构问题决定了由凯莱表给出的两个群是否同构。对于阶数为n的群，Tarjan在20世纪70年代提出了一个运行时间为n（logn+O（1））的算法（米勒，STOC 1978）。尽管在过去的几十年中进行了广泛的研究，但目前最好的群同构算法的运行时间为ann（1 / 4 +o（1））logn（Rosenbaum 2013）。（幂零）类2和指数p的p-群的同构测试已被确定为获得群同构问题的anno（logn）时间算法的主要障碍。虽然2类p-群和指数p-群的代数结构比一般群简单得多，但该类p-群的同构判定算法的运行时间也是O（logn），本文给出了2类p-群和指数p-群的同构判定算法，对任意素数p> 2，其运行时间为O（（logn）5/6）.我们的结果是基于对反对称矩阵元组等距问题的一种新的简化（Ivanyos和Qiao，SIAM J. Computing，2019）。为了获得减少，我们开发了几种工具，矩阵空间分析，包括矩阵空间个性化细化方法和低秩矩阵空间的表征。
The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with ordern, an algorithm withn(logn+O(1))running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has ann(1 / 4 +o(1))lognrunning time (Rosenbaum 2013).The isomorphism testing forp-groups of (nilpotent) class 2 and exponentphas been identified as a major barrier to obtaining anno(logn)time algorithm for the group isomorphism problem. Although thep-groups of class 2 and exponentphave much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has annO(logn)running time.In this paper, we present an isomorphism testing algorithm forp-groups of class 2 and exponentpwith running timenO((logn)5/6)for any primep> 2. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces.
登录
查看更多内容
对于大多数订单来说，群同构的时间几乎是线性的
DOI：
--
发表时间：
2020
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
H. Dietrich;James B. Wilson
通讯作者：
James B. Wilson
具有固定次正规链的群同构
DOI：
--
发表时间：
2015
期刊：
arXiv.org
影响因子：
--
作者：
E. Luks
通讯作者：
E. Luks
关于具有正规霍尔子群的群的同构检验
DOI：
--
发表时间：
2012
期刊：
Journal of Computational Science and Technology
影响因子：
--
作者：
Youming Qiao;Jayalal Sarma;Bangsheng Tang
通讯作者：
Bangsheng Tang
打破 p 群同构的生成器枚举界限
DOI：
10.1016/j.tcs.2015.05.036
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
David J. Rosenbaum;Fabian Wagner
通讯作者：
Fabian Wagner
没有阿贝尔正规子群的群的多项式时间同构检验 -（扩展摘要）
DOI：
10.1007/978-3-642-31594-7_5
发表时间：
2012
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
L. Babai;Paolo Codenotti;Youming Qiao
通讯作者：
Youming Qiao