90 citations · 330 across the 36 of their papers we have counts for
6 papers · 1 filter
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…