11 citations · 31 across the 5 of their papers we have counts for
8 papers
On the Group and Color Isomorphism Problems
François Le Gall, David J. Rosenbaum
In this paper, we prove results on the relationship between the complexity of the group and color isomorphism problems. The difficulty of color isomorphism problems is known to be…
Beating the Generator-Enumeration Bound for Solvable-Group Isomorphism
David J. Rosenbaum
We consider the isomorphism problem for groups specified by their multiplication tables. Until recently, the best published bound for the worst-case was achieved by the n^(log_p n…
Beating the Generator-Enumeration Bound for -Group Isomorphism
David J. Rosenbaum, Fabian Wagner
We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G cong H. For several decades, the n^(log_p n + O(1))…
Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing
David J. Rosenbaum
In this work, we introduce bidirectional collision detection --- a new algorithmic tool that applies to the collision problems that arise in many isomorphism problems. For the grou…
Breaking the n^(log n) Barrier for Solvable-Group Isomorphism
David Rosenbaum
We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G and H are isomorphic. The n^(log n) barrier for gro…
Optimal Quantum Circuits for Nearest-Neighbor Architectures
David Rosenbaum
We show that the depth of quantum circuits in the realistic architecture where a classical controller determines which local interactions to apply on the kD grid Z^k where k >= 2 i…