2020-08-01
Improved algorithms for alternating matrix space isometry: From theory to practice
Publication
Publication
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 Fp with some prime p 6= 2, solving AltMatSpIso in time pO(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 pO(n) when n and m are linearly related (FOCS’17). In this paper, we present an average-case algorithm for AltMatSpIso in time pO(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.
Additional Metadata | |
---|---|
, , , | |
doi.org/10.4230/LIPIcs.ESA.2020.26 | |
Leibniz International Proceedings in Informatics, LIPIcs | |
28th Annual European Symposium on Algorithms, ESA 2020 | |
Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
Brooksbank, P., Li, Y., Qiao, Y., & Wilson, J. (2020). Improved algorithms for alternating matrix space isometry: From theory to practice. In 28th Annual European Symposium on Algorithms (ESA 2020) (pp. 26:1–26:15). doi:10.4230/LIPIcs.ESA.2020.26 |