10 papers
Graph Isomorphism and Representation Theory
Joshua A. Grochow, Jacob Urisman
We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations ("separating modules," w…
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 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…
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…
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…
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…