90 citations · 330 across the 36 of their papers we have counts for
5 papers · 1 filter
Which groups are amenable to proving exponent two for matrix multiplication?
Jonah Blasiak, Thomas Church, Henry Cohn +2
The Cohn-Umans group-theoretic approach to matrix multiplication suggests embedding matrix multiplication into group algebra multiplication, and bounding in terms of the repres…
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…
Designing Strassen's algorithm
Joshua A. Grochow, Cristopher Moore
In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than . While the recursive construction in his algori…
Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines
Maxinder S. Kanwal, Joshua A. Grochow, Nihat Ay
In the past three decades, many theoretical measures of complexity have been proposed to help understand complex systems. In this work, for the first time, we place these measures…
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…