Document Open Access Logo

On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors

Authors Joshua A. Grochow , Youming Qiao

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.16.pdf
  • Filesize: 1.1 MB
  • 38 pages

Document Identifiers

Author Details

Joshua A. Grochow
  • Departments of Computer Science and Mathematics, University of Colorado Boulder, CO, USA
Youming Qiao
  • Centre for Quantum Software and Information, University of Technology Sydney, Australia

Funding

  • Grochow, Joshua A.: Partially supported during the preparation of this work by NSF Grants DMS-1750319 and CCF-2047756.
  • Qiao, Youming: Partially supported during the preparation of this work by NSF Grant DMS-1750319 and Australian Research Council Grant DP200100950.

Acknowledgements

The authors would like to thank James B. Wilson for related discussions, and Ryan Williams for pointing out the problem of distinguishing between ETH and #ETH. J. A. G. would like to thank V. Futorny and V. V. Sergeichuk for their collaboration on the related work (Futorny, Grochow, and Sergeichuk, Lin. Alg. Appl., 2019). Ideas leading to this work originated from the 2015 workshop "Wildness in computer science, physics, and mathematics" at the Santa Fe Institute.

Cite As Get BibTex

Joshua A. Grochow and Youming Qiao. On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.16

Abstract

In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, and work in the model of matrix groups over finite fields. Our main results are as follows.  
- Although search-to-decision and counting-to-decision reductions have been known for over four decades for Graph Isomorphism (GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within p-groups of class 2 and exponent p.
- Despite the widely held belief that p-groups of class 2 and exponent p are the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing of p-groups of "small" class and exponent p to those of class two and exponent p. 
For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of GI. Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard Correspondence with Tensor Isomorphism-completeness results (Grochow & Qiao, ibid.).

Subject Classification

ACM Subject Classification
  • Computing methodologies → Algebraic algorithms
  • Theory of computation → Problems, reductions and completeness
Keywords
  • group isomorphism
  • search-to-decision reduction
  • counting-to-decision reduction
  • nilpotent group isomorphism
  • p-group isomorphism
  • tensor isomorphism

Metrics

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

Related Versions

References

  1. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. Inf. Comput., 256:2-8, 2017. URL: https://doi.org/10.1016/j.ic.2017.04.004.
  2. Vikraman Arvind and Jacobo Torán. Isomorphism testing: Perspective and open problems. Bulletin of the EATCS, 86:66-84, 2005. Google Scholar
  3. 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.03547 [cs.DS] version 2. URL: https://doi.org/10.1145/2897518.2897542.
  4. László Babai, Paolo Codenotti, Joshua A. Grochow, and Youming Qiao. Code equivalence and group isomorphism. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11), pages 1395-1408, Philadelphia, PA, 2011. SIAM. URL: https://doi.org/10.1137/1.9781611973082.107.
  5. László Babai, Paolo Codenotti, and Youming Qiao. Polynomial-time isomorphism test for groups with no abelian normal subgroups - (extended abstract). In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings, Part I, pages 51-62, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_5.
  6. László Babai and Youming Qiao. Polynomial-time isomorphism test for groups with Abelian Sylow towers. In 29th STACS, pages 453-464. Springer LNCS 6651, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.453.
  7. Reinhold Baer. Groups with abelian central quotient group. Trans. AMS, 44(3):357-386, 1938. URL: https://doi.org/10.1090/S0002-9947-1938-1501972-1.
  8. Mihir Bellare and Shafi Goldwasser. The complexity of decision versus search. SIAM J. Comput., 23(1):97-119, 1994. URL: https://doi.org/10.1137/S0097539792228289.
  9. Hans Ulrich Besche and Bettina Eick. Construction of finite groups. J. Symb. Comput., 27(4):387-404, 1999. URL: https://doi.org/10.1006/jsco.1998.0258.
  10. Hans Ulrich Besche, Bettina Eick, and E.A. O'Brien. A millennium project: Constructing small groups. Intern. J. Alg. and Comput, 12:623-644, 2002. URL: https://doi.org/10.1142/S0218196702001115.
  11. Anton Betten, Michael Braun, Harald Fripertinger, Adalbert Kerber, Axel Kohnert, and Alfred Wassermann. Error-correcting linear codes: Classification by isometry and applications, volume 18. Springer Science and Business Media, 2006. Google Scholar
  12. Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, and James B. Wilson. Incorporating Weisfeiler-Leman into algorithms for group isomorphism. https://arxiv.org/abs/1905.02518 [cs.CC], 2019. Google Scholar
  13. Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson. Improved algorithms for alternating matrix space isometry: From theory to practice. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 26:1-26:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.26.
  14. Peter A. Brooksbank and Eugene M. Luks. Testing isomorphism of modules. J. Algebra, 320(11):4020-4029, 2008. URL: https://doi.org/10.1016/j.jalgebra.2008.07.014.
  15. Peter A. Brooksbank, Joshua Maglione, and James B. Wilson. A fast isomorphism test for groups whose Lie algebra has genus 2. J. Algebra, 473:545-590, 2017. URL: https://doi.org/10.1016/j.jalgebra.2016.12.007.
  16. Peter A. Brooksbank and E. A. O'Brien. Constructing the group preserving a system of forms. Internat. J. Algebra Comput., 18(2):227-241, 2008. URL: https://doi.org/10.1142/S021819670800441X.
  17. John J. Cannon and Derek F. Holt. Automorphism group computation and isomorphism testing in finite groups. J. Symbolic Comput., 35(3):241-267, 2003. URL: https://doi.org/10.1016/S0747-7171(02)00133-5.
  18. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):Art. 14, 57, 2009. URL: https://doi.org/10.1145/1516512.1516516.
  19. Alexander Chistov, Gábor Ivanyos, and Marek Karpinski. Polynomial time algorithms for modules over finite dimensional algebras. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC '97, pages 68-74. ACM, 1997. URL: https://doi.org/10.1145/258726.258751.
  20. Serena Cicalò, Willem A. de Graaf, and Michael Vaughan-Lee. An effective version of the Lazard correspondence. J. Algebra, 352(1):430-450, 2012. URL: https://doi.org/10.1016/j.jalgebra.2011.11.031.
  21. W.A. de Graaf. Lie Algebras: Theory and Algorithms, volume 56 of North-Holland Mathematical Library. Elsevier Science, 2000. Google Scholar
  22. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms, 10(4):Art. 21, 32, 2014. URL: https://doi.org/10.1145/2635812.
  23. Sean Eberhard and Stefan-C. Virchow. Random generation of the special linear group. Transactions of the American Mathematical Society, page 1, 2020. URL: https://doi.org/10.1090/tran/8009.
  24. Wayne Eberly and Mark Giesbrecht. Efficient decomposition of associative algebras over finite fields. Journal of Symbolic Computation, 29(3):441-458, 2000. URL: https://doi.org/10.1006/jsco.1999.0308.
  25. Bettina Eick, C. R. Leedham-Green, and E. A. O'Brien. Constructing automorphism groups of p-groups. Comm. Algebra, 30(5):2271-2295, 2002. URL: https://doi.org/10.1081/AGB-120003468.
  26. V. Felsch and J. Neubüser. On a programme for the determination of the automorphism group of a finite group. In Pergamon J. Leech, editor, Computational Problems in Abstract Algebra (Proceedings of a Conference on Computational Problems in Algebra, Oxford, 1967), pages 59-60, Oxford, 1970. Google Scholar
  27. Katalin Friedl and Lajos Rónyai. Polynomial time solutions of some problems in computational algebra. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 153-162. ACM, 1985. URL: https://doi.org/10.1145/22145.22162.
  28. Vyacheslav Futorny, Joshua A. Grochow, and Vladimir V. Sergeichuk. Wildness for tensors. Lin. Alg. Appl., 566:212-244, 2019. URL: https://doi.org/10.1016/j.laa.2018.12.022.
  29. Joshua A. Grochow. Answer to "what is the hardest instance for the group isomorphism problem?". Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/a/42551/129.
  30. Joshua A. Grochow and Youming Qiao. Polynomial-time isomorphism test of groups that are tame extensions - (extended abstract). In Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 578-589, 2015. URL: https://doi.org/10.1007/978-3-662-48971-0_49.
  31. Joshua A. Grochow and Youming Qiao. Algorithms for group isomorphism via group extensions and cohomology. SIAM J. Comput., 46(4):1153-1216, 2017. Preliminary version in IEEE Conference on Computational Complexity (CCC) 2014 (DOI:10.1109/CCC.2014.19). Also available as https://arxiv.org/abs/1309.1776 [cs.DS] and ECCC Technical Report TR13-123. URL: https://doi.org/10.1137/15M1009767.
  32. Joshua A. Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness. In ITCS, page to appear, 2021. URL: https://arxiv.org/abs/1907.00309.
  33. Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Commun. ACM, 63(11):128-134, 2020. URL: https://doi.org/10.1145/3372123.
  34. Xiaoyu He and Youming Qiao. On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions. https://arxiv.org/abs/2003.07200 [math.CO], 2020. Google Scholar
  35. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. System Sci., 62(2):367-375, 2001. Special issue on the Fourteenth Annual IEEE Conference on Computational Complexity (Atlanta, GA, 1999). URL: https://doi.org/10.1006/jcss.2000.1727.
  36. Gábor Ivanyos. Fast randomized algorithms for the structure of matrix algebras over finite fields. In Proceedings of the 2000 international symposium on Symbolic and algebraic computation, pages 175-183. ACM, 2000. URL: https://doi.org/10.1145/345542.345620.
  37. Gábor Ivanyos, Marek Karpinski, and Nitin Saxena. Deterministic polynomial time algorithms for matrix completion problems. SIAM J. Comput., 39(8):3736-3751, 2010. URL: https://doi.org/10.1137/090781231.
  38. Gábor Ivanyos and Lajos Rónyai. Computations in associative and Lie algebras. In Some tapas of computer algebra, pages 91-120. Springer, 1999. URL: https://doi.org/10.1007/978-3-662-03891-8_5.
  39. Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun. General linear group action on tensors: A candidate for post-quantum cryptography. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part I, volume 11891 of Lecture Notes in Computer Science, pages 251-281. Springer, 2019. Preprint https://arxiv.org/abs/1906.04330 [cs.CR]. URL: https://doi.org/10.1007/978-3-030-36030-6_11.
  40. William M. Kantor. Some topics in asymptotic group theory. Groups, Combinatorics and Geometry (Durham, pages 403-421, 1990. Google Scholar
  41. William M Kantor and Alexander Lubotzky. The probability of generating a finite classical group. Geometriae Dedicata, 36(1):67-87, 1990. Google Scholar
  42. Neeraj Kayal and Timur Nezhmetdinov. Factoring groups efficiently. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, volume 5555 of Lecture Notes in Computer Science, pages 585-596. Springer, 2009. Preprint ECCC Tech. Report TR08-074. URL: https://doi.org/10.1007/978-3-642-02927-1_49.
  43. E. I. Khukhro. p-automorphisms of finite p-groups, volume 246 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1998. URL: https://doi.org/10.1017/CBO9780511526008.
  44. Johannes Köbler, Uwe Schöning, and Jacobo Torán. The graph isomorphism problem: its structural complexity. Birkhauser Verlag, Basel, Switzerland, Switzerland, 1993. URL: https://doi.org/10.1007/978-1-4612-0333-9.
  45. Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3):455-500, 2009. URL: https://doi.org/10.1137/07070111X.
  46. Michel Lazard. Sur les groupes nilpotents et les anneaux de Lie. Ann. Sci. Ecole Norm. Sup. (3), 71:101-190, 1954. URL: https://doi.org/10.24033/asens.1021.
  47. François Le Gall. Efficient isomorphism testing for a class of group extensions. In Proc. 26th STACS, pages 625-636, 2009. URL: https://doi.org/10.4230/LIPIcs.STACS.2009.1830.
  48. Mark L. Lewis and James B. Wilson. Isomorphism in expanding families of indistinguishable groups. Groups Complex. Cryptol., 4(1):73-110, 2012. URL: https://doi.org/10.1515/gcc-2012-0008.
  49. Yinan Li and Youming Qiao. Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 463-474. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.49.
  50. Richard J. Lipton, Lawrence Snyder, and Yechezkel Zalcstein. The complexity of word and isomorphism problems for finite groups. Yale University Department of Computer Science Research Report # 91, 1977. URL: https://apps.dtic.mil/dtic/tr/fulltext/u2/a053246.pdf.
  51. Eugene M. Luks. Computing in solvable matrix groups. In FOCS 1992, 33rd Annual Symposium on Foundations of Computer Science, pages 111-120. IEEE Computer Society, 1992. URL: https://doi.org/10.1109/SFCS.1992.267813.
  52. Eugene M. Luks. Permutation groups and polynomial-time computation. In Groups and computation (New Brunswick, NJ, 1991), volume 11 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 139-175. Amer. Math. Soc., Providence, RI, 1993. Google Scholar
  53. Eugene M. Luks. Hypergraph isomorphism and structural equivalence of boolean functions. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 652-658, 1999. URL: https://doi.org/10.1145/301250.301427.
  54. Rudolf Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131-136, 1979. Google Scholar
  55. Brendan D. McKay. Practical graph isomorphism. Congr. Numer., pages 45-87, 1980. Google Scholar
  56. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60(0):94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
  57. Alan H. Mekler. Stability of nilpotent groups of class 2 and prime exponent. The Journal of Symbolic Logic, 46(4):781-788, 1981. Google Scholar
  58. Gary L. Miller. On the n^log n isomorphism technique (a preliminary report). In STOC, pages 51-58. ACM, 1978. URL: https://doi.org/10.1145/800133.804331.
  59. Takunari Miyazaki. Luks’s reduction of graph isomorphism to code equivalence. Comment to E. W. Clark, https://groups.google.com/forum/#!msg/sci.math.research/puZxGj9HXKI/CeyH2yyyNFUJ, 1996.
  60. Vipul Naik. Lazard correspondence up to isoclinism. PhD thesis, The University of Chicago, 2013. URL: https://vipulnaik.com/thesis/.
  61. Jacques Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, pages 33-48, 1996. URL: https://doi.org/10.1007/3-540-68339-9_4.
  62. Erez Petrank and Ron M. Roth. Is code equivalence easy to decide? IEEE Trans. Inf. Theory, 43(5):1602-1604, 1997. URL: https://doi.org/10.1109/18.623157.
  63. Youming Qiao, Jayalal M. N. Sarma, and Bangsheng Tang. On isomorphism testing of groups with normal Hall subgroups. In Proc. 28th STACS, pages 567-578, 2011. URL: https://doi.org/10.4230/LIPIcs.STACS.2011.567.
  64. Lajos Rónyai. Computing the structure of finite algebras. J. Symb. Comput., 9(3):355-373, 1990. URL: https://doi.org/10.1016/S0747-7171(08)80017-X.
  65. David J. Rosenbaum. Bidirectional collision detection and faster deterministic isomorphism testing. arXiv preprint https://arxiv.org/abs/1304.3935 [cs.DS], 2013. Google Scholar
  66. David J. Rosenbaum. Breaking the n^log n barrier for solvable-group isomorphism. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1054-1073. SIAM, 2013. Preprint https://arxiv.org/abs/1205.0642 [cs.DS]. URL: https://doi.org/10.1137/1.9781611973105.76.
  67. Nicolas Sendrier and Dimitris E. Simos. The hardness of code equivalence over 𝔽_q and its application to code-based cryptography. In International Workshop on Post-Quantum Cryptography, pages 203-216. Springer, 2013. Google Scholar
  68. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. URL: https://doi.org/10.1137/0220053.
  69. Leslie G. Valiant. Relative complexity of checking and evaluating. Information Processing Lett., 5(1):20-23, 1976/77. URL: https://doi.org/10.1016/0020-0190(76)90097-1.
  70. James 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
  71. James B. Wilson. Decomposing p-groups via Jordan algebras. J. Algebra, 322(8):2642-2679, 2009. URL: https://doi.org/10.1016/j.jalgebra.2009.07.029.
  72. James B. Wilson. Finding direct product decompositions in polynomial time. https://arxiv.org/abs/1005.0548 [math.GR], 2010. Google Scholar
  73. James B. Wilson. Existence, algorithms, and asymptotics of direct product decompositions, I. Groups Complex. Cryptol., 4(1):33-72, 2012. URL: https://doi.org/10.1515/gcc-2012-0007.
  74. V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich. Graph isomorphism problem. J. Soviet Math., 29(4):1426-1481, May 1985. URL: https://doi.org/10.1007/BF02104746.
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 About DROPS Imprint Privacy Contact