18 citations · 38 across the 10 of their papers we have counts for
10 papers
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…
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 records
Andrew Berdahl, Uttam Bhat, Vanessa Ferdinand +12
World record setting has long attracted public interest and scientific investigation. Extremal records summarize the limits of the space explored by a process, and the historical p…
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…