90 citations · 330 across the 36 of their papers we have counts for
23 papers · 1 filter
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.…
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…
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…
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…
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…
Computational topology and the Unique Games Conjecture
Joshua A. Grochow, Jamie Tucker-Foltz
Covering spaces of graphs have long been useful for studying expanders (as "graph lifts") and unique games (as the "label-extended graph"). In this paper we advocate for the thesis…
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of…
Towards an algebraic natural proofs barrier via polynomial identity testing
Joshua A. Grochow, Mrinal Kumar, Michael Saks +1
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if a…
Matrix multiplication algorithms from group orbits
Joshua A. Grochow, Cristopher Moore
We show how to construct highly symmetric algorithms for matrix multiplication. In particular, we consider algorithms which decompose the matrix multiplication tensor into a sum of…
NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications
Joshua A. Grochow
Mahaney's Theorem states that, assuming , no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an expos…
Boundaries of VP and VNP
Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = , where VP is the class of…
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"…
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…
Circuit complexity, proof complexity, and polynomial identity testing
Joshua A. Grochow, Toniann Pitassi
We introduce a new algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolea…
Unifying and generalizing known lower bounds via geometric complexity theory
Joshua A. Grochow
We show that most arithmetic circuit lower bounds and relations between lower bounds naturally fit into the representation-theoretic framework suggested by geometric complexity the…
Report on "Mathematical Aspects of P vs. NP and its Variants."
Joshua A. Grochow, Korben Rusek
This is a report on a workshop held August 1 to August 5, 2011 at the Institute for Computational and Experimental Research in Mathematics (ICERM) at Brown University, Providence,…
Complexity Classes of Equivalence Problems Revisited
Lance Fortnow, Joshua A. Grochow
To determine if two lists of numbers are the same set, we sort both lists and see if we get the same result. The sorted list is a canonical form for the equivalence relation of set…