On the nlog n isomorphism technique (A Preliminary Report)

DOI10.1145/800133.804331zbMath1282.68192OpenAlexW1989188127MaRDI QIDQ5402540

Gary Lee Miller

Publication date: 14 March 2014

Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/800133.804331

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Loops, quasigroups (20N05) Graph algorithms (graph-theoretic aspects) (05C85) Triple systems (05B07) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Algorithms for Group Isomorphism via Group Extensions and Cohomology, On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, On nondeterminism in parallel computation, On isomorphism testing of groups with normal Hall subgroups, Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed, Linear time algorithms for Abelian group isomorphism and related problems, Steiner triple systems of order 19 with nontrivial automorphism group, Computing Autotopism Groups of Partial Latin Rectangles, Computational complexity of reconstruction and isomorphism testing for designs and line graphs, On deciding switching equivalence of graphs, Complexity bounds for equivalence and isomorphism of latin squares, Algorithms and complexity for counting configurations in Steiner triple systems, Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting), Concerning the complexity of deciding isomorphism of block designs, Unnamed Item, Isomorphism of graphs of bounded valence can be tested in polynomial time, Bounds on the number of autotopisms and subsquares of a Latin square, On the automorphism groups of strongly regular graphs. II., Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing, Constructive complexity, Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice, Beating the generator-enumeration bound for \(p\)-group isomorphism, A parallelization of Miller's \(n^{\log n}\) isomorphism technique, Nearly linear time isomorphism algorithms for some nonabelian group classes, Graph isomorphism, general remarks, Permutation group approach to association schemes, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Subcomplete generalizations of graph isomorphism, Graph isomorphism problem, Combinatorial analysis (nonnegative matrices, algorithmic problems), Nondeterministics circuits, space complexity and quasigroups