19 citations · 56 across the 22 of their papers we have counts for
6 papers · 1 filter
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…
Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
Elise Tate, Joshua A. Grochow
Graphs are a powerful tool for analyzing large data sets, but many real-world phenomena involve interactions that go beyond the simple pairwise relationships captured by a graph. I…
On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
Joshua A. Grochow, Michael Levet
In this paper, we show that the constant-dimensional Weisfeiler-Leman algorithm for groups (Brachter & Schweitzer, LICS 2020) can be fruitfully used to improve parallel complexity…
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms
Joshua A. Grochow, Youming Qiao, Gang Tang
We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we…
Designing Strassen's algorithm
Joshua A. Grochow, Cristopher Moore
In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than . While the recursive construction in his algori…
Polynomial-time isomorphism test of groups that are tame extensions
Joshua A. Grochow, Youming Qiao
We give new polynomial-time algorithms for testing isomorphism of a class of groups given by multiplication tables (GpI). Two results (Cannon & Holt, J. Symb. Comput. 2003; Babai,…