1 Search Results for "Brooksbank, Peter A."

Document
DOI: 10.4230/LIPIcs.ESA.2020.26
Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice

Authors: Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

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 𝔽_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.
Cite as

Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson. Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brooksbank_et_al:LIPIcs.ESA.2020.26,
  author =	{Brooksbank, Peter A. and Li, Yinan and Qiao, Youming and Wilson, James B.},
  title =	{{Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.26},
  URN =		{urn:nbn:de:0030-drops-128920},
  doi =		{10.4230/LIPIcs.ESA.2020.26},
  annote =	{Keywords: Alternating Matrix Spaces, Average-case Algorithm, p-groups of Class 2nd Exponent p, Magma}
}
  • Refine by Author
  • 1 Brooksbank, Peter A.
  • 1 Li, Yinan
  • 1 Qiao, Youming
  • 1 Wilson, James B.

  • Refine by Classification
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 1 Alternating Matrix Spaces
  • 1 Average-case Algorithm
  • 1 Magma
  • 1 p-groups of Class 2nd Exponent p

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact