90 citations · 330 across the 36 of their papers we have counts for
48 papers
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.…
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…
Gröbner Bases Native to Term-ordered Commutative Algebras, with Application to the Hodge Algebra of Minors
Joshua A. Grochow, Abhiram Natarajan
Motivated by better understanding the bideterminant (=product of minors) basis on the polynomial ring in variables, we develop theory \& algorithms for Gröbner bases i…
On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
Joshua A. Grochow, Dan Johnson, Michael Levet
In this paper, we exhibit an isomorphism test for groups without Abelian normal subgroups (a.k.a. Fitting-free groups), a class for which isomorphism testing was…
Finite matrix multiplication algorithms from infinite groups
Jonah Blasiak, Henry Cohn, Joshua A. Grochow +2
The Cohn-Umans (FOCS '03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group satisfying a s…
On the Constant-Depth Circuit Complexity of Generating Quasigroups
Nathaniel A. Collins, Joshua A. Grochow, Michael Levet +1
We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for group…
On the Descriptive Complexity of Groups without Abelian Normal Subgroups (Extended Abstract)
Joshua A. Grochow, Michael Levet
In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht-Fraisse bijective pebble game in Hella's (Ann. Pure Ap…
Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system
Joshua A. Grochow
The Ideal Proof System (IPS) of Grochow & Pitassi (FOCS 2014, J. ACM, 2018) is an algebraic proof system that uses algebraic circuits to refute the solvability of unsatisfiable sys…
On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
Joshua A. Grochow, Youming Qiao
Many isomorphism problems for tensors, groups, algebras, and polynomials were recently shown to be equivalent to one another under polynomial-time reductions, prompting the introdu…
On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
Zhili Chen, Joshua A. Grochow, Youming Qiao +2
We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. Such pro…
On the algebraic proof complexity of Tensor Isomorphism
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi +1
The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essen…
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality
Joshua A. Grochow
There is no single canonical polynomial-time version of the Axiom of Choice (AC); several statements of AC that are equivalent in Zermelo-Fraenkel (ZF) set theory are already inequ…
On the Descriptive Complexity of Groups without Abelian Normal Subgroups
Joshua A. Grochow, Michael Levet
In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht--Fraïssé bijective pebble game in Hella's (Ann. Pure A…
Experience Report: Standards-Based Grading at Scale in Algorithms
Lijun Chen, Joshua A. Grochow, Ryan Layer +1
We report our experiences implementing standards-based grading at scale in an Algorithms course, which serves as the terminal required CS Theory course in our department's undergra…
Matrix multiplication via matrix groups
Jonah Blasiak, Henry Cohn, Joshua A. Grochow +2
In 2003, Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of grou…
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…
An Improved Algorithm for Coarse-Graining Cellular Automata
Yerim Song, Joshua A. Grochow
In studying the predictability of emergent phenomena in complex systems, Israeli & Goldenfeld (Phys. Rev. Lett., 2004; Phys. Rev. E, 2006) showed how to coarse-grain (elementary) c…
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…
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions
Joshua A. Grochow, Youming Qiao
In this paper we consider the problems of testing isomorphism of tensors, -groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learni…
Incorporating Weisfeiler-Leman into algorithms for group isomorphism
Peter A. Brooksbank, Joshua A. Grochow, Yinan Li +2
In this paper we combine many of the standard and more recent algebraic techniques for testing isomorphism of finite groups (GpI) with combinatorial techniques that have typically…