2013/04/14 by David J. Rosenbaum, Rosenbaum, David J. · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #semigroups and automata theory #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1304.3935
In this work, we introduce bidirectional collision detection --- a new\nalgorithmic tool that applies to the collision problems that arise in many\nisomorphism problems. For the group isomorphism problem, we show that\nbidirectional collision detection yields a deterministic n^((1 / 2) log n +\nO(1)) time algorithm whereas previously the n^(log n + O(1))\ngenerator-enumeration algorithm was the best result for several decades. For\nthe hard special case of solvable groups, we combine bidirectional collision\ndetection with methods from the author's previous work to obtain a\ndeterministic square-root speedup over the best previous algorithm. We also\nshow a deterministic square-root speedup over the best previous algorithm for\ntesting isomorphism of rings. We can even apply bidirectional collision\ndetection to the graph isomorphism problem to obtain a deterministic T^(1 /\nsqrt(2)) speedup over the best previous deterministic algorithm. Although the\nspace requirements for our algorithms are greater than those for previous\ndeterministic isomorphism tests, we show time-space tradeoffs that interpolate\nbetween the resource requirements of our algorithms and previous work.\n