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 (31)

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

This page was built for publication: On the n^{log n} isomorphism technique (A Preliminary Report)