Document Open Access Logo

Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.26.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Peter A. Brooksbank
  • Department of Mathematics, Bucknell University, Lewisburg, PA, USA
Yinan Li
  • CWI and QuSoft, Amsterdam, The Netherlands
Youming Qiao
  • Centre for Quantum Software and Information, University of Technology Sydney, Ultimo, Australia
James B. Wilson
  • Department of Mathematics, Colorado State University, Fort Collins, CO, USA

Funding

The authors would like to acknowledge the financial support by NSF grant DMS-1750319.
  • Brooksbank, Peter A.: Partially supported by NSF grant DMS-1620362.
  • Li, Yinan: Partially supported by ERC Consolidator Grant 615307-QPROGRESS.
  • Qiao, Youming: Partially supported by the Australian Research Council DE150100720 and DP200100950.
  • Wilson, James B.: Partially supported by NSF grant DMS-1620454.

Acknowledgements

The authors would like to acknowledge László Babai and Xiaorui Sun for discussions, and Joshua A. Grochow for discussions and comments on improving the presentation. The authors acknowledge the Hausdorff Institute for Mathematics, the University of Auckland, the Santa Fe Institute, and the TACA workshop at the University of Colorado, Boulder and Colorado State University, where this research was carried out by (subsets of) the authors.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ESA.2020.26

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.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Algebraic algorithms
  • Computing methodologies → Combinatorial algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Alternating Matrix Spaces
  • Average-case Algorithm
  • p-groups of Class 2nd Exponent p
  • Magma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. László Babai. Graph Isomorphism in Quasipolynomial Time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 684-697, 2016. https://arxiv.org/abs/1512.03547v2. URL: https://doi.org/10.1145/2897518.2897542.
  2. László Babai, Paul Erdős, and Stanley M. Selkow. Random Graph Isomorphism. SIAM Journal on Computing, 9(3):628-635, 1980. URL: https://doi.org/10.1137/0209047.
  3. László Babai and Ludek Kucera. Canonical Labelling of Graphs in Linear Average Time. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 39-46, 1979. URL: https://doi.org/10.1109/SFCS.1979.8.
  4. Reinhold Baer. Groups with Abelian Central Quotient Group. Transactions of the American Mathematical Society, 44(3):357-386, 1938. URL: https://doi.org/10.2307/1989886.
  5. Peter A. Brooksbank, Joshua A. Grochow Grochow, Yinan Li, Youming Qiao, and James B. Wilson. Incorporating Weisfeiler-Leman into Algorithms for Group Isomorphism, 2019. arXiv. URL: http://arxiv.org/abs/1905.02518.
  6. Peter A. Brooksbank, Joshua Maglione, and James B. Wilson. TheTensor.Space. URL: https://github.com/thetensor-space/.
  7. Peter A. Brooksbank, Joshua Maglione, and James B. Wilson. A Fast Isomorphism Test for Groups whose Lie Algebra has Genus 2. Journal of Algebra, 473:545-590, 2017. URL: https://doi.org/10.1016/j.jalgebra.2016.12.007.
  8. Peter A. Brooksbank and Eamonn A. O'Brien. Constructing the Group Preserving a System of Forms. International Journal of Algebra and Computation, 18(02):227-241, 2008. URL: https://doi.org/10.1142/S021819670800441X.
  9. Peter A. Brooksbank and James B. Wilson. Computing Isometry Groups of Hermitian Maps. Transactions of the American Mathematical Society, 364(4):1975-1996, 2012. URL: https://doi.org/10.2307/41524909.
  10. Paul Erdős and Alfréd Rényi. On Random Graphs I. Publicationes Mathematicae Debrecen, 6:290-297, 1959. Google Scholar
  11. Volkmar Felsch and Joachim Neubüser. On a Programme for the Determination of the Automorphism Group of a Finite Group. In Computational Problems in Abstract Algebra, pages 59-60. Pergamon, 1970. URL: https://doi.org/10.1016/B978-0-08-012975-4.50011-4.
  12. Joshua A. Grochow and Youming Qiao. Algorithms for Group Isomorphism via Group Extensions and Cohomology. SIAM Journal on Computing, 46(4):1153-1216, 2017. URL: https://doi.org/10.1137/15M1009767.
  13. Joshua A. Grochow and Youming Qiao. Isomorphism Problems for Tensors, Groups, and Cubic Forms: Completeness and Reductions, 2019. arXiv. URL: http://arxiv.org/abs/1907.00309.
  14. Hermann Heineken and Hans Liebeck. The Occurrence of Finite Groups in the Automorphism Group of Nilpotent Groups of Class 2. Archiv der Mathematik, 25:8-16, 1974. URL: https://doi.org/10.1007/BF01238631.
  15. Harald Andrés Helfgott, Jitendra Bajpai, and Daniele Dona. Graph Isomorphisms in Quasi-polynomial Time, 2017. arXiv. URL: http://arxiv.org/abs/1710.04574.
  16. Gábor Ivanyos, Marek Karpinski, and Nitin Saxena. Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal on Computing, 39(8):3736-3751, 2010. URL: https://doi.org/10.1137/090781231.
  17. Gábor Ivanyos and Youming Qiao. Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing. SIAM Journal on Computing, 48(3):926-963, 2019. URL: https://doi.org/10.1137/18M1165682.
  18. Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun. General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography. In Theory of Cryptography, pages 251-281, 2019. URL: https://doi.org/10.1007/978-3-030-36030-6_11.
  19. Telikepalli Kavitha. Linear Time Algorithms for Abelian Group Isomorphism and Related Problems. Journal of Computer and System Sciences, 73(6):986-996, 2007. URL: https://doi.org/10.1016/j.jcss.2007.03.013.
  20. Mark L. Lewis and James B. Wilson. Isomorphism in Expanding Families of Indistinguishable Groups. Groups Complexity Cryptology, 4(1):73-110, 2012. URL: https://doi.org/10.1515/gcc-2012-0008.
  21. Yinan Li and Youming Qiao. Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 463-474, 2017. https://arxiv.org/abs/1708.04501v2. URL: https://doi.org/10.1109/FOCS.2017.49.
  22. Yinan Li and Youming Qiao. Group-theoretic Generalisations of Vertex and Edge Connectivities, 2019. arXiv. URL: http://arxiv.org/abs/1906.07948.
  23. Ruvim Lipyanski and Natalia Vanetik. On Borel Complexity of the Isomorphism Problems for Graph related Classes of Lie Algebras and Finite p-groups. Journal of Algebra and its Applications, 14(5):1550078, 15, 2015. URL: https://doi.org/10.1142/S0219498815500784.
  24. Eugene M. Luks. Permutation Groups and Polynomial-time Computation. In Groups and Computation, volume 11 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, 1993. Google Scholar
  25. Eugene M. Luks. Hypergraph Isomorphism and Structural Equivalence of Boolean Functions. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing STOC, pages 652-658. ACM, 1999. URL: https://doi.org/10.1145/301250.301427.
  26. Gary L. Miller. On the n log n Isomorphism Technique (A Preliminary Report). In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, page 51–58, New York, NY, USA, 1978. Association for Computing Machinery. URL: https://doi.org/10.1145/800133.804331.
  27. David J. Rosenbaum. Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing, 2013. arXiv. URL: http://arxiv.org/abs/1304.3935.
  28. David J. Rosenbaum and Fabian Wagner. Beating the Generator-enumeration Bound for p-group Isomorphism. Theoretical Computer Science, 593:16-25, 2015. URL: https://doi.org/10.1016/j.tcs.2015.05.036.
  29. James B. Wilson. 2014 conference on Groups, Computation, and Geometry at Colorado State University, co-organized by P. Brooksbank, A. Hulpke, T. Penttila, J. Wilson, and W. Kantor. Personal communication, 2014. Google Scholar
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