Brooksbank, Peter A. ;
Li, Yinan ;
Qiao, Youming ;
Wilson, James B.
Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
Abstract
Motivated by testing isomorphism of pgroups, we study the alternating matrix space isometry problem (AltMatSpIso), which asks to decide whether two mdimensional subspaces of n×n alternating (skewsymmetric 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 pgroups 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 averagecase algorithm for AltMatSpIso in time p^O(n) when n and m are linearly related (FOCS '17). In this paper, we present an averagecase 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 averagecase analysis is stronger. We then implement our algorithm, with suitable modifications, in Magma. Our experiments indicate that it improves significantly over default (bruteforce) algorithms for this problem.
BibTeX  Entry
@InProceedings{brooksbank_et_al:LIPIcs:2020:12892,
author = {Peter A. Brooksbank and Yinan Li and Youming Qiao and James B. Wilson},
title = {{Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {26:126:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12892},
URN = {urn:nbn:de:0030drops128920},
doi = {10.4230/LIPIcs.ESA.2020.26},
annote = {Keywords: Alternating Matrix Spaces, Averagecase Algorithm, pgroups of Class 2nd Exponent p, Magma}
}
26.08.2020
Keywords: 

Alternating Matrix Spaces, Averagecase Algorithm, pgroups of Class 2nd Exponent p, Magma 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 