{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:21Z","timestamp":1750220781801,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,3]],"date-time":"2020-05-03T00:00:00Z","timestamp":1588464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-0916400 and CCF-1111382"],"award-info":[{"award-number":["CCF-0916400 and CCF-1111382"]}]},{"name":"Simons Award for Graduate Students in Theoretical Computer Science","award":["#316172"],"award-info":[{"award-number":["#316172"]}]},{"name":"Theoretical Physics at the Massachusetts Institute of Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>\n            We consider the isomorphism problem for groups specified by their multiplication tables. Until recently, the best published bound for the worst-case was achieved by the\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>log<\/jats:sup>\n            <jats:italic>p<\/jats:italic>\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n              +\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            generator-enumeration algorithm where\n            <jats:italic>n<\/jats:italic>\n            is the order of the group and\n            <jats:italic>p<\/jats:italic>\n            is the smallest prime divisor of\n            <jats:italic>n<\/jats:italic>\n            . In previous work with Fabian Wagner, we showed an\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>(1 \/ 2) log<\/jats:sup>\n            <jats:italic>p<\/jats:italic>\n            <jats:italic>\n              <jats:sup>n + O<\/jats:sup>\n            <\/jats:italic>\n            <jats:sup>\n              (log\n              <jats:italic>n<\/jats:italic>\n              \/ log log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            -time algorithm for testing isomorphism of\n            <jats:italic>p<\/jats:italic>\n            -groups by building graphs with degree bounded by\n            <jats:italic>p<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (1) that represent composition series for the groups and applying Luks\u2019 algorithm for testing isomorphism of bounded-degree graphs.\n          <\/jats:p>\n          <jats:p>\n            In this work, we extend this improvement to the more general class of solvable groups to obtain an\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>(1 \/ 2)<\/jats:sup>\n            log\n            <jats:italic>p<\/jats:italic>\n            <jats:sup>\n              <jats:italic>n + O<\/jats:italic>\n            <\/jats:sup>\n            <jats:sup>(log n \/ log log n)<\/jats:sup>\n            -time algorithm. In the case of solvable groups, the composition factors can be large which prevents previous methods from outperforming the generator-enumeration algorithm. Using Hall\u2019s theory of Sylow bases, we define a new object that generalizes the notion of a composition series with small factors but exists even when the composition factors are large. By constructing graphs that represent these objects and running Luks\u2019 algorithm, we obtain our algorithm for solvable-group isomorphism. We also extend our algorithm to compute canonical forms of solvable groups while retaining the same complexity.\n          <\/jats:p>","DOI":"10.1145\/3389396","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T22:58:44Z","timestamp":1588633124000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Beating the Generator-Enumeration Bound for Solvable-Group Isomorphism"],"prefix":"10.1145","volume":"12","author":[{"given":"David J.","family":"Rosenbaum","sequence":"first","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.107"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 39th International Colloquium on Automata, Languages and Programming. 51--62","author":"Babai L\u00e1szl\u00f3","year":"2012","unstructured":"L\u00e1szl\u00f3 Babai , Paolo Codenotti , and Youming Qiao . 2012 . Polynomial-time isomorphism test for groups with no Abelian normal subgroups (extended abstract) . In Proceedings of the 39th International Colloquium on Automata, Languages and Programming. 51--62 . L\u00e1szl\u00f3 Babai, Paolo Codenotti, and Youming Qiao. 2012. Polynomial-time isomorphism test for groups with no Abelian normal subgroups (extended abstract). In Proceedings of the 39th International Colloquium on Automata, Languages and Programming. 51--62."},{"volume-title":"Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 162--171","author":"Babai L.","key":"e_1_2_1_3_1","unstructured":"L. Babai , W. M. Kantor , and E. M. Luks . 1983. Computational complexity and the classification of finite simple groups . In Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 162--171 . L. Babai, W. M. Kantor, and E. M. Luks. 1983. Computational complexity and the classification of finite simple groups. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 162--171."},{"volume-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing. 171--183","author":"Babai L\u00e1szl\u00f3","key":"e_1_2_1_4_1","unstructured":"L\u00e1szl\u00f3 Babai and Eugene M. Luks . 1983. Canonical labeling of graphs . In Proceedings of the 15th Annual ACM Symposium on Theory of Computing. 171--183 . L\u00e1szl\u00f3 Babai and Eugene M. Luks. 1983. Canonical labeling of graphs. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing. 171--183."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science. 453--464","author":"Babai L\u00e1szl\u00f3","year":"2012","unstructured":"L\u00e1szl\u00f3 Babai and Youming Qiao . 2012 . Polynomial-time isomorphism test for groups with Abelian Sylow towers . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science. 453--464 . L\u00e1szl\u00f3 Babai and Youming Qiao. 2012. Polynomial-time isomorphism test for groups with Abelian Sylow towers. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science. 453--464."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"V. Felsch and J. Neub\u00fcser. 1970. On a programme for the determination of the automorphism group of a finite group. In Computational Problems in Abstract Algebra. 59--60.  V. Felsch and J. Neub\u00fcser. 1970. On a programme for the determination of the automorphism group of a finite group. In Computational Problems in Abstract Algebra. 59--60.","DOI":"10.1016\/B978-0-08-012975-4.50011-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700007760"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.19"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 26th International Symposium on Algorithms and Computation. 578--589","author":"Joshua","year":"1917","unstructured":"Joshua A. Grochow and Youming Qiao. 2015. Polynomial-time isomorphism test of groups that are tame extensions . In Proceedings of the 26th International Symposium on Algorithms and Computation. 578--589 . arXiv:1507.0 1917 Joshua A. Grochow and Youming Qiao. 2015. Polynomial-time isomorphism test of groups that are tame extensions. In Proceedings of the 26th International Symposium on Algorithms and Computation. 578--589. arXiv:1507.01917"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the London Mathematical Society s2-43","author":"Hall P.","year":"1938","unstructured":"P. Hall . 1938 . On the Sylow systems of a soluble group . Proceedings of the London Mathematical Society s2-43 , 1 (1938), 316--323. P. Hall. 1938. On the Sylow systems of a soluble group. Proceedings of the London Mathematical Society s2-43, 1 (1938), 316--323."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90002-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.013"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science. 625--636","author":"Gall Fran\u00e7ois Le","year":"2009","unstructured":"Fran\u00e7ois Le Gall . 2009 . Efficient isomorphism testing for a class of group extensions . In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science. 625--636 . arXiv:0812.2298 Fran\u00e7ois Le Gall. 2009. Efficient isomorphism testing for a class of group extensions. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science. 625--636. arXiv:0812.2298"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0008"},{"key":"e_1_2_1_16_1","unstructured":"Richard Lipton. 2011. An Annoying Open Problem. G\u00f6del\u2019s Lost Letter and P = NP. https:\/\/rjlipton.wordpress.com\/2011\/10\/08\/an-annoying-open-problem\/.  Richard Lipton. 2011. An Annoying Open Problem. G\u00f6del\u2019s Lost Letter and P = NP. https:\/\/rjlipton.wordpress.com\/2011\/10\/08\/an-annoying-open-problem\/."},{"key":"e_1_2_1_17_1","unstructured":"R. Lipton L. Snyder and Y. Zalcstein. 1977. The Complexity of Word and Isomorphism Problems for Finite Groups. Defense Technical Information Center.  R. Lipton L. Snyder and Y. Zalcstein. 1977. The Complexity of Word and Isomorphism Problems for Finite Groups. Defense Technical Information Center."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing. 51--58","author":"Miller Gary L.","year":"1978","unstructured":"Gary L. Miller . 1978 . On the nlogn isomorphism technique (A preliminary report) . In Proceedings of the 10th Annual ACM Symposium on Theory of Computing. 51--58 . Gary L. Miller. 1978. On the nlogn isomorphism technique (A preliminary report). In Proceedings of the 10th Annual ACM Symposium on Theory of Computing. 51--58."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science. 567--578","author":"Qiao Youming","year":"2011","unstructured":"Youming Qiao , Jayalal Sarma , and Bangsheng Tang . 2011 . On isomorphism testing of groups with normal Hall subgroups . In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science. 567--578 . Youming Qiao, Jayalal Sarma, and Bangsheng Tang. 2011. On isomorphism testing of groups with normal Hall subgroups. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science. 567--578."},{"volume-title":"A Course in the Theory of Groups","author":"Robinson D. J. S.","key":"e_1_2_1_21_1","unstructured":"D. J. S. Robinson . 1996. A Course in the Theory of Groups . Springer-Verlag . D. J. S. Robinson. 1996. A Course in the Theory of Groups. Springer-Verlag."},{"key":"e_1_2_1_22_1","volume-title":"Breaking the nlogn barrier for solvable-group isomorphism. (January","author":"Rosenbaum David J.","year":"2012","unstructured":"David J. Rosenbaum . 2012. Breaking the nlogn barrier for solvable-group isomorphism. (January 2012 ). arXiv:1205.0642 David J. Rosenbaum. 2012. Breaking the nlogn barrier for solvable-group isomorphism. (January 2012). arXiv:1205.0642"},{"key":"e_1_2_1_23_1","volume-title":"Bidirectional collision detection and faster deterministic isomorphism testing. (April","author":"Rosenbaum David J.","year":"2013","unstructured":"David J. Rosenbaum . 2013. Bidirectional collision detection and faster deterministic isomorphism testing. (April 2013 ). arXiv:1304.3935Submitted to Theoretical Computer Science . David J. Rosenbaum. 2013. Bidirectional collision detection and faster deterministic isomorphism testing. (April 2013). arXiv:1304.3935Submitted to Theoretical Computer Science."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. 1054--1073","author":"Rosenbaum David J.","year":"2013","unstructured":"David J. Rosenbaum . 2013 . Breaking the nlogn barrier for solvable-group isomorphism . In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. 1054--1073 . arXiv:1205.0642 David J. Rosenbaum. 2013. Breaking the nlogn barrier for solvable-group isomorphism. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. 1054--1073. arXiv:1205.0642"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.036"},{"volume-title":"Computer Studies Program","author":"Carla Savage. 1980. An An O(n2) Algorithm for Abelian Group Isomorphism.","key":"e_1_2_1_26_1","unstructured":"Carla Savage. 1980. An An O(n2) Algorithm for Abelian Group Isomorphism. Computer Studies Program , North Carolina State University . Carla Savage. 1980. An An O(n2) Algorithm for Abelian Group Isomorphism. Computer Studies Program, North Carolina State University."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0045"},{"key":"e_1_2_1_28_1","unstructured":"Fabian Wagner. 2011. On the Complexity of Group Isomorphism. Electronic Colloquium on Computational Complexity.  Fabian Wagner. 2011. On the Complexity of Group Isomorphism. Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_29_1","unstructured":"Fabian Wagner. 2012. On the Complexity of Group Isomorphism. Electronic Colloquium on Computational Complexity. Revision 2.  Fabian Wagner. 2012. On the Complexity of Group Isomorphism. Electronic Colloquium on Computational Complexity. Revision 2."},{"key":"e_1_2_1_30_1","volume-title":"Atti Secondo Congresso Un. Mat. Ital. Bologna","volume":"19","author":"Zappa Guido","year":"1940","unstructured":"Guido Zappa . 1940 . Sulla costruzione dei gruppi prodotto di due dati sottogruppi permutabili tra loro . In Atti Secondo Congresso Un. Mat. Ital. Bologna , Vol. 19 . 119--125. Guido Zappa. 1940. Sulla costruzione dei gruppi prodotto di due dati sottogruppi permutabili tra loro. In Atti Secondo Congresso Un. Mat. Ital. Bologna, Vol. 19. 119--125."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3389396","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3389396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:31Z","timestamp":1750200091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3389396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,3]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3389396"],"URL":"https:\/\/doi.org\/10.1145\/3389396","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,5,3]]},"assertion":[{"value":"2014-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}