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
I will not be in the office during the coronavirus pandemic. My virtual office is here on Zoom.
Fax: (303) 492-2844 (ATTN: me)
CS Theory @ CU Boulder
Complex Systems @ CU Boulder

Me @ Mastodon Twitter csthoery.SE mathoverflow ORCID
My pubs @ arXiv ECCC 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 and the Complex Systems Group. My research has two main thrusts (with deep underlying relations beneath):

For a taste of the deep underlying relations, check out this brief video.

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

(Mar 28, 2023) Gave a talk at ToniCS: Celebrating the Contributions and Influence of Toniann Pitassi, Working with Toni in Algebraic Proof Complexity.

(Mar 22, 2023) My student Michael Levet successfully defended his PhD thesis. Congratulations Michael!

(Mar 16, 2023) Guest blog post on the Computational Complexity Blog: Identities in Computational Complexity.

(Jan 27, 2023) Gave a talk at the U. Connecticut Logic Colloquium on my new paper Polynomial-time Axioms of Choice and polynomial-time cardinality.

(Jan 17, 2023) New paper posted Polynomial-time Axioms of Choice and polynomial-time cardinality to appear in a commemorative issue of Theory of Comput. Syst. dedicated to the memory of Alan L. Selman.

(Jan 11, 2023) Kevin Pratt presented at ITCS on our paper Matrix multiplication via matrix groups, joint with Jonah Blasiak, Henry Cohn, and Chris Umans.

(Nov 2022) Our now-former postdoc Nathan Lindzey begins his new postdoc position at the Technion. Congratulations Nathan!

(Sep 27, 2022) New paper posted: On the Descriptive Complexity of Groups without Abelian Normal Subgroups, joint with Michael Levet.

(Aug 23, 2022) Corrections and update to our preprint: On the parallel complexity of Group Isomorphism via Weisfeiler-Leman, joint with Michael Levet.

(May 16, 2022) My student Gabriel Andrade (co-advised with Rafael Frongillo), successfully defended his PhD Thesis. Congratulations Gabe!

(Apr 26, 2022) Presented "Polynomial Identity Testing & the Ideal Proof System" at the DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization on work in progress, to appear soon!

(Apr 26, 2022) New paper posted Experience Report: Standards-Based Grading at Scale in Algorithms, to appear at ITICSE '22, joint with Lijun Chen, Ryan Layer, and Michael Levet. My first ed paper!

(Apr 10, 2022) New paper posted Matrix multiplication via matrix groups, joint with Jonah Blasiak, Henry Cohn, Kevin Pratt, and Chris Umans.

(Apr 2, 2022) Undergraduate research assistant job opportunity for Summer '22 (mid-May thru mid-August). Duties include working with me and/or my graduate students on a mutually agreed upon computational complexity research project. Pay is $15.00/hr. Apply by emailing me directly with CV/resume and transcript (unofficial is fine), as well as some indication of your relevant research interests. Update May 4 2022: applications now closed.

(Feb 7, 2022) Invited speaker at FOCS '21 (in '22) Workshop: Reflections on Propositional Proofs in Algorithms & Complexity. My slides are also available. Paired talk with Toniann Pitassi (my part starts ~35 minutes in, but you should watch hers too!).

See all past updates