文章基本信息

标题：Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
本地全文：下载
作者：Peter A. Brooksbank ; Yinan Li ; Youming Qiao 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：26:1-26:15
DOI：10.4230/LIPIcs.ESA.2020.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Motivated by testing isomorphism of p-groups, we study the alternating matrix space isometry problem (AltMatSpIso), which asks to decide whether two m-dimensional subspaces of nÃ-n alternating (skew-symmetric if the field is not of characteristic 2) matrices are the same up to a change of basis. Over a finite field ð"½_p with some prime pâ 2, solving AltMatSpIso in time p^O(n+m) is equivalent to testing isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. The latter problem has long been considered a bottleneck case for the group isomorphism problem. Recently, Li and Qiao presented an average-case algorithm for AltMatSpIso in time p^O(n) when n and m are linearly related (FOCS '17). In this paper, we present an average-case algorithm for AltMatSpIso in time p^O(n+m). Besides removing the restriction on the relation between n and m, our algorithm is considerably simpler, and the average-case analysis is stronger. We then implement our algorithm, with suitable modifications, in Magma. Our experiments indicate that it improves significantly over default (brute-force) algorithms for this problem.
关键词：Alternating Matrix Spaces; Average-case Algorithm; p-groups of Class 2nd Exponent p; Magma