Picture of Joshua A. Grochow Joshua A. Grochow
Assistant Professor
Department of Computer Science
University of Colorado at Boulder
[first name].[last name]@cs.colorado.edu
CS Theory @ CU Boulder
Omidyar Fellow
Santa Fe Institute
[first initial][lastname]@santafe.edu
Office phone: (505) 946-2789
Me @ Twitter csthoery.SE mathoverflow ORCID
My pubs @ arXiv ECCC (ECCC too) DBLP MathSciNet Google Scholar

About Me

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

I am currently on leave from CU Boulder until Summer 2017, in order to finish my Omidyar Postdoctoral Fellowship at SFI. 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

(Oct 24, 2016) Gave a talk at UT Austin: "Wildness at the heart of complexity." I'll be around Monday, Tuesday, and Thursday this week. Email me if you'd like to meet!

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

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

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