90 citations · 330 across the 36 of their papers we have counts for
5 papers · 1 filter
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Joshua A. Grochow, Gábor Ivanyos, Youming Qiao +1
The finite group isomorphism problem asks whether two finite groups of order are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in time $N^{…
Faster network motif discovery by counting isomorphic subtrees
Tarek Tohme, Joshua A. Grochow
We develop a new algorithm for counting the number of subgraphs of a network isomorphic to a given query graph (#SubgraphIsomorphism), motivated by network motif search. High-degre…
Algorithms for Finite Group Epimorphism Testing
Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
The Group Epimorphism Problem (GpEpi) asks, given two finite groups and , whether there exists a surjective group homomorphism, or epimorphism, from to . When…
Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2 Circuits and Lower Bounds
Joshua A. Grochow, Gülce Kardeş, Michael Levet
In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Is…
Geometric Complexity Theory and Graph Isomorphism
Joshua A. Grochow, Jacob Urisman
We investigate ideas from the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001) in the setting of graph isomorphism.…