2.2k citations · 3.3k across the 34 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.CC2017
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…
cs.DS2017★ 1 cited
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…
cond-mat.stat-mech2017★ 14 cited
Percolation Thresholds in Hyperbolic Lattices
Stephan Mertens, Cristopher Moore
We use invasion percolation to compute numerical values for bond and site percolation thresholds (existence of an infinite cluster) and (uniqueness of the infinite clus…