Picture of Joshua A. Grochow Joshua A. Grochow
Assistant Professor
Departments of Computer Science and Mathematics
University of Colorado at Boulder
[first initial][last name]@colorado.edu
(303) 735-7618
CS Theory @ CU Boulder

Me @ Twitter csthoery.SE mathoverflow ORCID
My pubs @ arXiv ECCC (ECCC too) DBLP MathSciNet Google Scholar SciRate

About Me

I am an Assistant Professor in the Departments of Computer Science and Mathematics at the University of Colorado at Boulder, where I am a member of the CS Theory Group. My research has two main thrusts (with deep underlying relations beneath):

I was previously an Omidyar Fellow at the interdisciplinary Santa Fe Institute for complex systems. Prior to SFI, I was a postdoc in the University of Toronto CS Theory Group, and prior to that I got my Ph.D. at the University of Chicago.

What's new

(Jul 7, 2017) The final, open access version of Algorithms for group isomorphism via group extensions and cohomology has now appeared in SIAM Journal on Computation! Joint with Youming Qiao. Open access forever thanks to funding from the Santa Fe Institute.

(Jun 30, 2017) I am now officially, by courtesy, also an Assistant Professor in the Department of Mathematics!

(Jun 23, 2017) Comparing information-theoretic measures of complexity in Boltzmann machines accepted to Entropy! Joint with my former REU student from SFI (now at Berkeley), Max Kanwal, and Nihat Ay.

(May 11, 2017) New paper posted: On the records, joint with the Santa Fe Institute postdocs. This paper was the result of our second (annual?) "72 Hours of Science" event, in which we conceived, developed, executed, and wrote up an entire scientific project in only 72 hours (albeit with a team of 15 postdocs)! See the Appendix of the paper for a little more detail. Comments and suggestions are more than welcome.

(Apr 18, 2017) On cap sets and the group-theoretic approach to matrix multiplication invited as a plenary talk at the STOC TheoryFest, which highlights some of the best CS theory work from any venue in the past two years!

(Apr 3, 2017) Algorithms for group isomorphism via group extensions and cohomology accepted to SIAM Journal on Computing! See the improved results and exposition due to the refereeing process in the updated arXiv version. Joint with Youming Qiao. To appear any day now...

(Jan 16, 2017) On cap sets and the group-theoretic approach to matrix multiplication accepted to Discrete Analysis. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, Eric Naslund, Will Sawin, and Chris Umans.

(Jan 8, 2017) New paper posted: Towards an algebraic natural proofs barrier via polynomial identity testing, joint with Mrinal Kumar, Mike Saks, and Shubhangi Saraf.

(Dec 31, 2016) Excited to be part of the NetSci 2017 program committee!

(Dec 15, 2016) Excited to be part of the FOCS 2017 program committee!

(Dec 6, 2016) New preprint posted: Matrix multiplication algorithms from group orbits, joint with Cris Moore.

(Dec 3, 2016) New paper posted: A quantitative definition of organismality and its application to lichen, led by Eric Libby, joint with Simon DeDeo and David Wolpert.

(Oct 24, 2016) Gave a talk at UT Austin: "Wildness at the heart of complexity."

(Oct 19, 2016) New paper posted: NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications.

(Oct 18, 2016) New CS Theory Group website launched for CU Boulder. Come join us!

(Aug 18, 2016) The onion decomposition accepted to Scientific Reports!

(Aug 15, 2016) Started as Assistant Professor at CU Boulder Computer Science! I'm officially on leave until Summer 2017, in order to finish my current postdoc. But I'm still looking for Ph.D. students to start in 2017, as well as other theory colleagues who might join us!

(Aug 10, 2016) Paper updated: On cap sets and the group-theoretic approach to matrix multiplication. Results extended from vector spaces over finite fields to arbitrary abelian groups of bounded exponent, and made a new connection to geometric invariant theory. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, Eric Naslund, Will Sawin, and Chris Umans.

(July 27, 2016) Monotone projection lower bounds from extended formulation lower bounds accepted to Theory of Computing, where it now enters the "print queue," awaiting (I think) copy editing.

See all past updates