On the Weisfeiler-Leman dimension of finite groups. (English) Zbl 1498.20002
Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 287-300 (2020).
MSC:
| 20-08 | Computational methods for problems pertaining to group theory |
| 20D60 | Arithmetic and combinatorial problems involving abstract finite groups |
| 03C13 | Model theory of finite structures |
| 03B60 | Other nonclassical logic |
Keywords:
Cai-Frer-Immermann graphs; Weisfeiler-Leman dimension; group isomorphism; logics with countingReferences:
| [1] | László Babai. 2016. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, Daniel Wichs and Yishay Mansour (Eds.). ACM, 684-697. https://doi.org/10.1145/2897518.2897542 · Zbl 1376.68058 |
| [2] | László Babai, Paolo Codenotti, Joshua A. Grochow, and Youming Qiao. 2011. Code Equivalence and Group Isomorphism. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, Dana Randall (Ed.). SIAM, 1395-1408. https://doi.org/10.1137/1.9781611973082.107 · Zbl 1382.20037 |
| [3] | László Babai, Paolo Codenotti, and Youming Qiao. 2012. Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract). In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I (Lecture Notes in Computer Science), Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (Eds.), Vol. 7391. Springer, 51-62. https://doi.org/10.1007/978-3-642-31594-7_5 · Zbl 1272.68475 |
| [4] | László Babai and Youming Qiao. 2012. Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France (LIPIcs), Christoph Dürr and Thomas Wilke (Eds.), Vol. 14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 453-464. https://doi.org/10.4230/LIPIcs.STACS.2012.453 · Zbl 1248.20001 |
| [5] | Jendrik Brachter and Pascal Schweitzer. 2020. On the Weisfeiler-Leman Dimension of Finite Groups. CoRR abs/2003.13745 (2020). arXiv:arXiv:2003.13745 arXiv. · Zbl 1498.20002 |
| [6] | Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, and James B. Wilson. 2019. Incorporating Weisfeiler-Leman into algorithms for group isomorphism. CoRR abs/1905.02518 (2019). arXiv:1905.02518 http://arxiv.org/abs/1905.02518 arXiv. |
| [7] | Peter A. Brooksbank, Joshua Maglione, and James B. Wilson. 2017. A fast isomorphism test for groups whose Lie algebra has genus 2. J. Algebra 473 (2017), 545-590. https://doi.org/10.1016/j.jalgebra.2016.12.007 · Zbl 1406.20008 |
| [8] | Jin-Yi Cai, Martin Fürer, and Neil Immerman. 1992. An optimal lower bound on the number of variables for graph identifications. Combinatorica 12, 4 (1992), 389-410. https://doi.org/10.1007/BF01305232 · Zbl 0785.68043 |
| [9] | Peter J. Cameron. 1992. Projective and polar spaces. QMW Maths Notes, Vol. 13. Queen Mary and Westfield College, School of Mathematical Sciences, London. viii+147 pages. |
| [10] | John J. Cannon and Derek F. Holt. 2003. Automorphism Group Computation and Isomorphism Testing in Finite Groups. J. Symb. Comput. 35, 3 (March 2003), 241âĂŞ267. https://doi.org/10.1016/S0747-7171(02)00133-5 · Zbl 1032.20016 |
| [11] | Bireswar Das and Shivdutt Sharma. 2019. Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes. In Computer Science - Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 15, 2019, Proceedings (Lecture Notes in Computer Science), René van Bevern and Gregory Kucherov (Eds.), Vol. 11532. Springer, 80-92. https://doi.org/10.1007/978-3-030-19955-5_8 · Zbl 1491.20005 |
| [12] | Heiko Dietrich and James B. Wilson. 2018. Polynomial-time isomorphism testing of groups of most finite orders. CoRR abs/1806.08872 (2018). arXiv:arXiv:1806.08872 arXiv. |
| [13] | Bettina Eick, Charles R. Leedham-Green, and Eamonn A. O’Brien. 2002. Constructing automorphism groups of p-groups. Comm. Algebra 30, 5 (2002), 2271-2295. https://doi.org/10.1081/AGB-120003468 · Zbl 1006.20001 |
| [14] | François Le Gall. 2009. Efficient Isomorphism Testing for a Class of Group Extensions. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings (LIPIcs), Susanne Albers and Jean-Yves Marion (Eds.), Vol. 3. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 625-636. https://doi.org/10.4230/LIPIcs.STACS.2009.1830 · Zbl 1236.68106 |
| [15] | George Glauberman and Łukasz Grabowski. 2015. Groups with Identical k-Profiles. Theory Comput. 11, 15 (2015), 395-401. https://doi.org/10.4086/toc.2015.v011a015 · Zbl 1341.20014 |
| [16] | Walid Gomaa. 2010. Descriptive Complexity of Finite Abelian Groups. Int. J. Algebra Comput. 20, 8 (2010), 1087-1116. https://doi.org/10.1142/S0218196710006047 · Zbl 1209.03026 |
| [17] | Timothy Gowers. Blog entry: November 7, 2011, Comment: November 12, 2011. Comment on Dick Lipton’s blog: The Group isomorphism Problem: A Possible Polymath Problem? (Blog entry: November 7, 2011, Comment: November 12, 2011). https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-polymath-problem/https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-polymath-problem/. |
| [18] | Joshua A. Grochow and Youming Qiao. 2017. Algorithms for Group Isomorphism via Group Extensions and Cohomology. SIAM J. Comput. 46, 4 (2017), 1153-1216. https://doi.org/10.1137/15M1009767 · Zbl 1475.20001 |
| [19] | Martin Grohe. 2000. Isomorphism testing for embeddable graphs through definability. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000, May 21-23, Portland, OR, USA, F. Frances Yao and Eugene M. Luks (Eds.). ACM, 63-72. https://doi.org/10.1145/335305.335313 · Zbl 1296.05134 |
| [20] | Martin Grohe. 2017. Descriptive complexity, canonisation, and definable graph structure theory. Lecture Notes in Logic, Vol. 47. Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge. · Zbl 1530.68007 |
| [21] | Lauri Hella. 1996. Logical Hierarchies in PTIME. Inf. Comput. 129, 1 (1996), 1-19. https://doi.org/10.1006/inco.1996.0070 · Zbl 0864.68095 |
| [22] | Neil Immerman and Eric Lander. 1990. Describing graphs: a first-order approach to graph canonization. In Complexity theory retrospective. Springer, New York, 59-81. |
| [23] | Neil Immerman and Rik Sengupta. 2019. The k-Dimensional Weisfeiler-Leman Algorithm. CoRR abs/1907.09582 (2019). arXiv:arXiv:1907.09582 arXiv. |
| [24] | Gábor Ivanyos and Youming Qiao. 2019. Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing. SIAM J. Comput. 48, 3 (2019), 926-963. https://doi.org/10.1137/18M1165682 · Zbl 1422.68116 |
| [25] | Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. 2019. The Weisfeiler-Leman Dimension of Planar Graphs Is at Most 3. J. ACM 66, 6 (2019), 44:1-44:31. https://doi.org/10.1145/3333003 · Zbl 1483.05048 |
| [26] | Yinan Li and Youming Qiao. 2017. 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, Berkeley, CA, USA, October 15-17, 2017, Chris Umans (Ed.). IEEE Computer Society, 463-474. https://doi.org/10.1109/FOCS.2017.49 |
| [27] | Eugene M. Luks. 2015. Group Isomorphism with Fixed Subnormal Chains. CoRR abs/1511.00151 (2015). arXiv:arXiv:1511.00151 http://arxiv.org/abs/1511.00151 arXiv. |
| [28] | Alan H. Mekler. 1981. Stability of nilpotent groups of class 2 and prime exponent. Journal of Symbolic Logic 46, 4 (1981), 781âĂŞ788. https://doi.org/10.2307/2273227 · Zbl 0482.03014 |
| [29] | Gary L. Miller. 1978. On the nlog n Isomorphism Technique: A preliminary report. In Proceedings of Tenth Annual ACM Symposium on Theory of Computing, STOC 1978 (San Diego, California, USA) (STOC âĂŹ78). ACM, Association for Computing Machinery, New York, NY, USA, 51âĂŞ58. https://doi.org/10.1145/800133.804331 · Zbl 1282.68192 |
| [30] | André Nies and Katrin Tent. 2017. Describing finite groups by short first-order sentences. Israel J. Math. 221, 1 (2017), 85-115. https://doi.org/10.1007/s11856-017-1563-2 · Zbl 1403.03059 |
| [31] | Eamonn A. O’Brien. 1994. Isomorphism testing for p-groups. J. Symbolic Comput. 17, 2 (1994), 131, 133-147. https://doi.org/10.1006/jsco.1994.1007 · Zbl 0824.20020 |
| [32] | Martin Otto. 2017. Bounded Variable Logics and Counting: A Study in Finite Models. Lecture Notes in Logic, Vol. 9. Cambridge University Press. https://doi.org/10.1017/9781316716878 · Zbl 0869.03018 |
| [33] | Youming Qiao, Jayalal Sarma, and Bangsheng Tang. 2012. On Isomorphism Testing of Groups with Normal Hall Subgroups. J. Comput. Sci. Technol. 27, 4 (2012), 687-701. https://doi.org/10.1007/s11390-012-1255-7 · Zbl 1280.68111 |
| [34] | David J. Rosenbaum. 2013. Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing. CoRR abs/1304.3935 (2013). arXiv:arXiv:1304.3935 http://arxiv.org/abs/1304.3935 arXiv. |
| [35] | David J. Rosenbaum and Fabian Wagner. 2015. Beating the generator-enumeration bound for p-group isomorphism. Theor. Comput. Sci. 593 (2015), 16-25. https://doi.org/10.1016/j.tcs.2015.05.036 · Zbl 1330.68124 |
| [36] | Michael J. Smith. 1996. Computing automorphisms of finite soluble groups. B. Aust. Math. Soc. 53, 1 (1996), 169âĂŞ171. https://doi.org/10.1017/S0004972700016841 · Zbl 0845.20017 |
| [37] | Boris Weisfeiler. 1976. On construction and identification of graphs. Springer-Verlag, Berlin-New York. xiv+237 pages. · Zbl 0366.05019 |
| [38] | Daniel Wiebking. 2020. Normalizes and permutational isomorphisms in simply-exponential time. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, Shuchi Chawla (Ed.). SIAM, 230-238. https://doi.org/10.1137/1.9781611975994.14 · Zbl 07304037 |
| [39] | James B. Wilson. 2008. Group Decompositions, Jordan Algebras, and Algorithms for p-groups. Ph.D. Dissertation. University of Oregon. |
| [40] | James B. Wilson. 2016. The threshold for subgroup profiles to agree is Ω(log n). CoRR abs/1612.01444 (2016). arXiv:1612.01444 https://arxiv.org/abs/1612.01444 arXiv. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
