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
ECES 118E   (303) 735-7438
CS Theory @ CU Boulder

I'm looking for Ph.D. students and a postdoc!
Me @ Twitter csthoery.SE mathoverflow ORCID
My pubs @ arXiv ECCC DBLP MathSciNet Google Scholar SciRate

Updates

(Due Jan 31, 2018) We're soliciting applications for a Postdoctoral Fellowship beginning 2018! Algebraic/geometric complexity, spectral algorithms, unique games, and more with me and Alex Kolla. Check out our theory group.

(Due Dec 15, 2018) I'm seeking Ph.D. students, in computational complexity and/or complex systems & networks. Apply here!

(Dec 7, 2017) New paper posted: Which groups are amenable to proving exponent two for matrix multiplication? Joint with Jonah Blasiak, Thomas Church, Henry Cohn, and Chris Umans. In which, among other things, we give a nonabelian generalization of the Croot-Lev-Pach-Ellenberg-Gijswijt method.

(Dec 5, 2017) Speaking in the CU Boulder Math Lie Theory seminar: Representation theory and additive combinatorics in algorithms for matrix multiplication.

(Nov 14, 2017) Gave CU Boulder Kempner Colloquium in the Math Department: "Wildness & geometry in representation theory & computational complexity."

(Oct 23, 2017) New paper posted: Minimum circuit size, graph isomorphism, and related problems! Joint with Eric Allender, Dieter van Melkebeek, Cris Moore, and Andrew Morgan.

(Oct 6, 2017) Gave a talk at the Rocky Mountain Algebraic Combinatorics Seminar in Fort Collins: Representation theory and additive combinatorics in algorithms for matrix multiplication.

(Sep 1, 2017) New paper posted: Designing Strassen's algorithm, showing a clean proof of Strassen's algorithm using only a simple unitary 2-design in two dimensions. Joint with Cris Moore.

(Sep 1, 2017) New paper posted: Designing Strassen's algorithm, showing a clean proof of Strassen's algorithm using only a simple unitary 2-design in two dimensions.

(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.

2016 Updates

(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.

(May 29, 2016) Excited to be part of the CCC 2017 Program Committee!

(May 26, 2016) Gave a talk in the Philadelphia area Combinatorics and Algebraic Geometry (CAGE) seminar: "Newton polytopes of quiver semi-invariants in geometric complexity theory," on (part of) this paper.

(May 23, 2016) New paper posted: On cap sets and the group-theoretic approach to matrix multiplication. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, and Chris Umans.

(May 11, 2016) Full version of Boundaries of VP and VNP now available as an arXiv preprint.

(April 27, 2016) "Boundaries of VP and VNP" accepted to ICALP 2016! Joint with Ketan Mulmuley and Youming Qiao.

(April 12, 2016) Story by Jennifer Ouellette on Dynamics of beneficial epidemics, and how we produced it in just 72 Hours of Science.

(April 12, 2016) Gave a CS colloquium at CU Boulder: "What makes individual problem instances hard? Computational complexity and complex systems." You can watch the video here.

(April 7, 2016) New paper posted: Dynamics of beneficial epidemics, joint with the Santa Fe Institute postdocs. This paper was the result of our "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 14 postdocs)! See the Appendix of the paper for a little more detail. Comments and suggestions are more than welcome.

(March 29, 2016) Gave a talk at the UW CS Theory Seminar: Combinatorial polytopes in algebraic and geometric complexity theory, about this paper and a forthcoming paper with Ketan Mulmuley and Youming Qiao.

2015 Updates

(December 20, 2015) Quoted several times in a WIRED front-page article by Erica Klarreich about the recent breakthrough on Graph Isomorphism (reprinted from Quanta).

(November 3, 2015) Updated Monotone projection lower bounds from extended formulation lower bounds with new lower bound against reductions from perfect matchings in general graphs to perfect matchings in bipartite graphs.

(October 29, 2015) New paper posted: Network structure at multiple scales via a new network statistic: the onion decomposition, joint with Laurent Hébert-Dufresne and Antoine Allard.

(October 28, 2015) New paper posted: Monotone projection lower bounds from extended formulation lower bounds.

(October 12-16, 2015) Organized the SFI Workshop on Wildness in Computer Science, Physics, and Mathematics.

(October 8, 2015) New paper posted: Graph isomorphism and circuit size, joint with Eric Allender and Cris Moore.

(October 1, 2015) Eric Allender gave a great 15-minute talk at the Simons Institute for the Theory of Computing on our most recent joint work with Cris Moore, "Graph Isomorphism and Circuit Size."



(August 31, 2015) Polynomial-time isomorphism test of groups that are tame extensions accepted to ISAAC 2015 (the leading conference on algorithms in (East) Asia).

(July 14, 2015) You can listen to my interview by @Samuel_Hansen for the Strongly Connected Components podcast. My segment starts at 40:45, but you should also listen to the preceding interviews with my colleagues Yoav Kallus and Sid Redner!

(July 7, 2015) New paper posted: Polynomial-time isomorphism test of groups that are tame extensions (joint w/ Youming Qiao).

(May 9, 2015) The final, significantly expanded and edited version of Unifying known lower bounds via geometric complexity theory has now appeared in Computational Complexity, and is freely available forever (thanks to funding from SFI).

(Apr 21, 2015) Gave a CS colloquium at UNM: The role of symmetry (or the lack thereof) in algorithms and computational complexity.