1. Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
- Author
-
Brooksbank, PA, Li, Y, Qiao, Y, Wilson, JB, and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands
- Subjects
P-groups of Class 2and Exponent p ,Mathematics of computing → Graph algorithms ,Magma ,Computing methodologies → Combinatorial algorithms ,Computing methodologies → Algebraic algorithms ,Alternating Matrix Spaces ,Average-case Algorithm ,p-groups of Class 2nd Exponent p - Abstract
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 F with some prime p 6= 2, solving AltMatSpIso in time p 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 when n and m are linearly related (FOCS’17). In this paper, we present an average-case algorithm for AltMatSpIso in time p . 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. p O (n+m) O (n) O (n+m)
- Published
- 2020
- Full Text
- View/download PDF