90 citations · 330 across the 36 of their papers we have counts for
4 papers · 1 filter
Graph Isomorphism and Circuit Size
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2
It is well-known [KST93] that the complexity of the Graph Automorphism problem is characterized by a special case of Graph Isomorphism, where the input graphs satisfy the "promise"…
Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
Laurent Hébert-Dufresne, Joshua A. Grochow, Antoine Allard
We introduce a new network statistic that measures diverse structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and easy to interpr…
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
Joshua A. Grochow
In this short note, we reduce lower bounds on monotone projections of polynomials to lower bounds on extended formulations of polytopes. Applying our reduction to the seminal exten…
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,…