2026-07-20T07:30:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12892 2024-03-06T10:51:00Z ddc:004 open_access

Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice Brooksbank, Peter A. Li, Yinan Qiao, Youming Wilson, James B. Alternating Matrix Spaces Average-case Algorithm p-groups of Class 2nd Exponent p Magma 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter A. Brooksbank and Yinan Li and Youming Qiao and James B. Wilson 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.26 urn:nbn:de:0030-drops-128920 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode