90 citations · 330 across the 36 of their papers we have counts for
6 papers · 1 filter
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…
A quantitative definition of organismality and its application to lichen
Eric Libby, Joshua Grochow, Simon DeDeo +1
The organism is a fundamental concept in biology. However there is no universally accepted, formal, and yet broadly applicable definition of what an organism is. Here we introduce…
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…
On cap sets and the group-theoretic approach to matrix multiplication
Jonah Blasiak, Thomas Church, Henry Cohn +4
In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent of matrix multiplication by reducing matrix multiplication to group algebra multiplicatio…
Dynamics of beneficial epidemics
Andrew Berdahl, Christa Brelsford, Caterina De Bacco +12
Pathogens can spread epidemically through populations. Beneficial contagions, such as viruses that enhance host survival or technological innovations that improve quality of life,…