References

  1. Miklos Ajtai & Ronald Fagin (1990): Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic 55(1), pp. 113–150, doi:10.2307/2274958.
  2. Sanjeev Arora & Ronald Fagin (1997): On winning strategies in Ehrenfeucht–Fraïssé games. Theoretical Computer Science 174(1), pp. 97–121, doi:10.1016/S0304-3975(96)00015-1.
  3. V. Arvind & Piyush P. Kurur (2006): Graph Isomorphism is in SPP. Information and Computation 204(5), pp. 835–852, doi:10.1016/j.ic.2006.02.002.
  4. László Babai (2016): Graph isomorphism in quasipolynomial time [extended abstract]. In: STOC'16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, pp. 684–697, doi:10.1145/2897518.2897542. Preprint of full version at arXiv:1512.03547v2 [cs.DS].
  5. László Babai & Robert Beals (1999): A polynomial-time theory of black box groups I. In: Groups St Andrews 1997 in Bath, I, doi:10.1017/CBO9781107360228.004.
  6. László Babai, Robert Beals & Ákos Seress (2009): Polynomial-Time Theory of Matrix Groups. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09. Association for Computing Machinery, pp. 55–64, doi:10.1145/1536414.1536425.
  7. László Babai, Paolo Codenotti, Joshua A. Grochow & Youming Qiao (2011): Code equivalence and group isomorphism. In: Proceedings of the Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms (SODA11). SIAM, Philadelphia, PA, pp. 1395–1408, doi:10.1137/1.9781611973082.107.
  8. László Babai, Paolo Codenotti & Youming Qiao (2012): Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract). In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 51–62, doi:10.1007/978-3-642-31594-7_5.
  9. László Babai & Youming Qiao (2012): Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. In: 29th STACS. Springer LNCS 6651, pp. 453 – 464, doi:10.4230/LIPIcs.STACS.2012.453.
  10. Hans Ulrich Besche & Bettina Eick (1999): Construction of finite groups. J. Symb. Comput. 27(4), pp. 387–404, doi:10.1006/jsco.1998.0258.
  11. Hans Ulrich Besche, Bettina Eick & E.A. O'Brien (2002): A Millennium Project: Constructing Small Groups. Intern. J. Alg. and Comput 12, pp. 623–644, doi:10.1142/S0218196702001115.
  12. Jendrik Brachter & Pascal Schweitzer (2020): On the Weisfeiler–Leman Dimension of Finite Groups. In: Holger Hermanns, Lijun Zhang, Naoki Kobayashi & Dale Miller: LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020. ACM, pp. 287–300, doi:10.1145/3373718.3394786.
  13. Jendrik Brachter & Pascal Schweitzer (2021): A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler–Leman Dimension. arXiv:2111.11908 [math.GR].
  14. Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao & James B. Wilson (2019): Incorporating Weisfeiler–Leman into algorithms for group isomorphism. arXiv:1905.02518 [cs.CC].
  15. Peter A. Brooksbank, Joshua Maglione & James B. Wilson (2017): A fast isomorphism test for groups whose Lie algebra has genus 2. Journal of Algebra 473, pp. 545–590, doi:10.1016/j.jalgebra.2016.12.007.
  16. Harry Buhrman & Steven Homer (1992): Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. In: R. K. Shyamasundar: Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings, Lecture Notes in Computer Science 652. Springer, pp. 116–127, doi:10.1007/3-540-56287-7_99.
  17. Jin-Yi Cai, Martin Fürer & Neil Immerman (1992): An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), pp. 389–410, doi:10.1007/BF01305232. Originally appeared in SFCS '89.
  18. John J. Cannon & Derek F. Holt (2003): Automorphism group computation and isomorphism testing in finite groups. J. Symb. Comput. 35, pp. 241–267, doi:10.1016/S0747-7171(02)00133-5.
  19. Arkadev Chattopadhyay, Jacobo Torán & Fabian Wagner (2013): Graph isomorphism is not AC^0-reducible to group isomorphism. ACM Trans. Comput. Theory 5(4), pp. Art. 13, 13, doi:10.1145/2540088. Preliminary version appeared in FSTTCS '10; ECCC Tech. Report TR10-117.
  20. Bireswar Das & Shivdutt Sharma (2019): Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes. In: René van Bevern & Gregory Kucherov: Computer Science – Theory and Applications. Springer International Publishing, Cham, pp. 80–92, doi:10.1007/s00224-020-10010-z.
  21. Anuj Dawar & Bjarki Holm (2012): Pebble Games with Algebraic Rules. In: Artur Czumaj, Kurt Mehlhorn, Andrew Pitts & Roger Wattenhofer: Automata, Languages, and Programming. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 251–262, doi:10.1007/978-3-642-31585-5_25.
  22. Anuj Dawar & Danny Vagnozzi (2020): Generalizations of k-dimensional Weisfeiler–Leman stabilization. Moscow Journal of Combinatorics and Number Theory 9, pp. 229–252, doi:10.2140/moscow.2020.9.229.
  23. Heiko Dietrich & James B. Wilson (2022): Polynomial-time isomorphism testing for groups of most finite orders, doi:10.1109/FOCS52979.2021.00053.
  24. A. Ehrenfeucht (1960/61): An application of games to the completeness problem for formalized theories. Fund. Math. 49, pp. 129–141, doi:10.4064/fm-49-2-129-141.
  25. Bettina Eick, C. R. Leedham-Green & E. A. O'Brien (2002): Constructing automorphism groups of p-groups. Comm. Algebra 30(5), pp. 2271–2295, doi:10.1081/AGB-120003468.
  26. Jörg Flum & Martin Grohe (2000): On Fixed-Point Logic with Counting. The Journal of Symbolic Logic 65(2), pp. 777–787, doi:10.2307/2586569.
  27. Roland Fraïssé (1954): Sur quelques classifications des systèmes de relations. Publ. Sci. Univ. Alger. Sér. A 1, pp. 35–182 (1955).
  28. Walid Gomaa (2010): Descriptive Complexity of Finite Abelian Groups.. IJAC 20, pp. 1087–1116, doi:10.1142/S0218196710006047.
  29. Joshua A. Grochow & Michael Levet (2022): On the Descriptive Complexity of Groups without Abelian Normal Subgroups. ArXiv:2209.13725.
  30. Joshua A. Grochow & Michael Levet (2022): On the parallel complexity of Group Isomorphism and canonization via Weisfeiler–Leman. arXiv:2112.11487 [cs.DS].
  31. Joshua A. Grochow & Youming Qiao (2015): 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, pp. 578–589, doi:10.1007/978-3-662-48971-0_49.
  32. Martin Grohe (2017): Descriptive complexity, canonisation, and definable graph structure theory. Lecture Notes in Logic 47. Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge, doi:10.1017/9781139028868.
  33. Martin Grohe (2021): The logic of graph neural networks. In: LICS '21: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, doi:10.1109/LICS52264.2021.9470677. Preprint arXiv:2104.14624 [cs.LG].
  34. Martin Grohe & Sandra Kiefer (2019): A Linear Upper Bound on the Weisfeiler–Leman Dimension of Graphs of Bounded Genus. ArXiv:1904.07216.
  35. Martin Grohe & Sandra Kiefer (2021): Logarithmic Weisfeiler–Leman Identifies All Planar Graphs. ArXiv:2106.16218.
  36. Martin Grohe & Daniel Neuen (2019): Canonisation and Definability for Graphs of Bounded Rank Width. ArXiv:1901.10330.
  37. Martin Grohe & Martin Otto (2015): Pebble Games and linear equations. J. Symb. Log. 80(3), pp. 797–844, doi:10.1017/jsl.2015.28.
  38. Martin Grohe & Oleg Verbitsky (2006): Testing Graph Isomorphism in Parallel by Playing a Game. In: Michele Bugliesi, Bart Preneel, Vladimiro Sassone & Ingo Wegener: Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, Lecture Notes in Computer Science 4051. Springer, pp. 3–14, doi:10.1007/11786986_2.
  39. Xiaoyu He & Youming Qiao (2021): On the Baer–Lovász–Tutte construction of groups from graphs: Isomorphism types and homomorphism notions. Eur. J. Combin. 98, pp. 103404, doi:10.1016/j.ejc.2021.103404.
  40. Hermann Heineken & Hans Liebeck (1974): The occurrence of finite groups in the automorphism group of nilpotent groups of class 2. Arch. Math. (Basel) 25, pp. 8–16, doi:10.1007/BF01238631.
  41. Lauri Hella (1989): Definability hierarchies of generalized quantifiers. Annals of Pure and Applied Logic 43(3), pp. 235 – 271, doi:10.1016/0168-0072(89)90070-5.
  42. Lauri Hella (1996): Logical Hierarchies in PTIME. Information and Computation 129(1), pp. 1–19, doi:10.1006/inco.1996.0070.
  43. Neil Immerman (1986): Relational Queries Computable in Polynomial Time. Inf. Control. 68(1-3), pp. 86–104, doi:10.1016/S0019-9958(86)80029-8.
  44. Neil Immerman & Eric Lander (1990): Describing Graphs: A First-Order Approach to Graph Canonization. In: Alan L. Selman: Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988. Springer New York, New York, NY, pp. 59–81, doi:10.1007/978-1-4612-4478-3_5.
  45. Russell Impagliazzo, Ramamohan Paturi & Francis Zane (2001): Which Problems Have Strongly Exponential Complexity?. Journal of Computer and System Sciences 63(4), pp. 512–530, doi:10.1006/jcss.2001.1774.
  46. Gábor Ivanyos & 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), pp. 926–963, doi:10.1137/18M1165682.
  47. T. Kavitha (2007): Linear time algorithms for Abelian group isomorphism and related problems. Journal of Computer and System Sciences 73(6), pp. 986 – 996, doi:10.1016/j.jcss.2007.03.013.
  48. Neeraj Kayal & Timur Nezhmetdinov (2009): Factoring Groups Efficiently. In: Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas & Wolfgang Thomas: Automata, Languages and Programming. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 585–596, doi:10.1007/978-3-642-02927-1_49.
  49. Sandra Kiefer & Brendan D. McKay (2020): The Iteration Number of Colour Refinement. In: Artur Czumaj, Anuj Dawar & Emanuela Merelli: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), LIPIcs 168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 73:1–73:19, doi:10.4230/LIPIcs.ICALP.2020.73.
  50. Sandra Kiefer, Ilia Ponomarenko & Pascal Schweitzer (2019): The Weisfeiler–Leman Dimension of Planar Graphs Is at Most 3. J. ACM 66(6), doi:10.1145/3333003.
  51. Sandra Kiefer, Pascal Schweitzer & Erkal Selman (2022): Graphs Identified by Logics with Counting. ACM Trans. Comput. Log. 23(1), pp. 1:1–1:31, doi:10.1145/3417515.
  52. Johannes Köbler, Uwe Schöning & Jacobo Torán (1992): Graph Isomorphism is Low for PP. Comput. Complex. 2, pp. 301–330, doi:10.1007/BF01200427.
  53. Richard E. Ladner (1975): On the Structure of Polynomial Time Reducibility. J. ACM 22(1), pp. 155–171, doi:10.1145/321864.321877.
  54. François Le Gall (2009): Efficient Isomorphism Testing for a Class of Group Extensions. In: Proc. 26th STACS, pp. 625–636, doi:10.4230/LIPIcs.STACS.2009.1830.
  55. François Le Gall & David J. Rosenbaum (2016): On the Group and Color Isomorphism Problems. arXiv:1609.08253 [cs.CC].
  56. Mark L. Lewis & James B. Wilson (2012): Isomorphism in expanding families of indistinguishable groups. Groups - Complexity - Cryptology 4(1), pp. 73–110, doi:10.1515/gcc-2012-0008.
  57. P. Lindstrom (1966): First Order Predicate Logic with Generalized Quantifiers. Theoria 32(3), pp. 186–195, doi:10.1111/j.1755-2567.1966.tb00600.x.
  58. Alan H. Mekler (1981): Stability of Nilpotent Groups of Class 2 and Prime Exponent. The Journal of Symbolic Logic 46(4), pp. 781–788, doi:10.2307/2273227. Available at http://www.jstor.org/stable/2273227.
  59. Gary L. Miller (1978): On the n^ologn Isomorphism Technique (A Preliminary Report). In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC '78. Association for Computing Machinery, New York, NY, USA, pp. 51–58, doi:10.1145/800133.804331.
  60. Andrzej Mostowski (1957): On a generalization of quantifiers. Fundamenta Mathematicae 44(1), pp. 12–36, doi:10.4064/fm-44-1-12-36. Available at http://eudml.org/doc/213418.
  61. André Nies & Katrin Tent (2017): Describing finite groups by short first-order sentences. Israel J. Math. 221(1), pp. 85–115, doi:10.1007/s11856-017-1563-2.
  62. Youming Qiao, Jayalal M. N. Sarma & Bangsheng Tang (2011): On Isomorphism Testing of Groups with Normal Hall Subgroups. In: Proc. 28th STACS, pp. 567–578, doi:10.4230/LIPIcs.STACS.2011.567.
  63. David J. Rosenbaum (2013): Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing. arXiv:1304.3935 [cs.DS].
  64. Benjamin Rossman (2009): Ehrenfeucht–Fraïssé Games on Random Structures. In: Hiroakira Ono, Makoto Kanazawa & Ruy J. G. B. de Queiroz: Logic, Language, Information and Computation, 16th International Workshop, WoLLIC 2009, Tokyo, Japan, June 21-24, 2009. Proceedings, Lecture Notes in Computer Science 5514. Springer, pp. 350–364, doi:10.1007/978-3-642-02261-6_28.
  65. C. Savage (1980): An O(n^2) Algorithm for Abelian Group Isomorphism. Technical Report. North Carolina State University.
  66. Uwe Schöning (1988): Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences 37(3), pp. 312 – 323, doi:10.1016/0022-0000(88)90010-4.
  67. Moshe Y. Vardi (1982): The Complexity of Relational Query Languages (Extended Abstract). In: Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard & Lawrence H. Landweber: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA. ACM, pp. 137–146, doi:10.1145/800070.802186.
  68. Narayan Vikas (1996): An O(n) Algorithm for Abelian p-Group Isomorphism and an O(n ologn) Algorithm for Abelian Group Isomorphism. Journal of Computer and System Sciences 53(1), pp. 1–9, doi:10.1006/jcss.1996.0045.
  69. James B. Wilson (2012): Existence, algorithms, and asymptotics of direct product decompositions, I. Groups - Complexity - Cryptology 4(1), doi:10.1515/gcc-2012-0007.
  70. James B. Wilson (2019): The Threshold for Subgroup Profiles to Agree is Logarithmic. Theory of Computing 15(19), pp. 1–25, doi:10.4086/toc.2019.v015a019.
  71. V. N. Zemlyachenko, N. M. Korneenko & R. I. Tyshkevich (1985): Graph isomorphism problem. J. Soviet Math. 29(4), pp. 1426–1481, doi:10.1007/BF02104746.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org