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

Kevin Pratt presented Matrix multiplication via matrix groups at ITCS '23, based on this paper, joint with Jonah Blasiak, Henry Cohn, and Chris Umans.
Polynomial Identity Testing & the Ideal Proof System, at the DIMACS Workshop on Metacomplexity, Barriers, and Derandomization, April 2022
Algebraic proof complexity: a gentle introduction, a pair of talks by Toniann Pitassi and myself at the FOCS '21 (in '22) Workshop: Reflections on Propositional Proofs in Algorithms & Complexity. My slides are also available.
My expository talks at the 2021 School and Conference on Geometric Complexity Theory
- Representations in coordinate rings and partial stability
- Characterization by symmetries, natural proofs, and P vs NP in Geometric Complexity Theory
My CCC '21 talk On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors, based on this paper joint with Youming Qiao
Talks based partially or entirely on this paper joint with Cris Moore:
- 2020 LA Combinatorics & Complexity Seminar: Designing Strassen's algorithm for matrix multiplication
- 2021 Codes and Expansions (CodEx) Seminar talk: Codes and Expansions in Algorithms for Matrix Multiplication.
My ITCS '21 talk On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness and its shorter live version with Q&A This is part of this preprint, with Youming Qiao.
My talk Tensor Isomorphism from Banff BIRS 2019 Workshop on Algebraic Techniques in Computational Complexity, based on these three papers, joint in various combinations with Youming Qiao, Vyacheslav Futorny, Vladimir V. Sergeichuk, Peter A. Brooksbank, Yinan Li, and James B. Wilson.
My series of talks (plus quizzes) on complexityexplorer.org, giving a Introduction to Computation Theory. Including an algorithmic perspective on complex systems, in which I talk about how algorithms and complex systems are two sides of the same coin.
My 2015 REU students' final presentations:
- Sarah Brauner, Sorting and the information-theoretic lower bound: a structural analysis, on the REU project that turned into her undergraduate thesis The Structure of Partial Orders in the Face of Lower Bounds.
- Maxinder Kanwal, Total information flow in stochastic networks, on the project that would eventually turn into this paper
My 5-minute lightning research talk at the 2015 Santa Fe Institute Board Meeting, when I was an Omidyar Postdoctoral Fellow there.
Eric Allender's 15-minute talk at the Simons Institute on our joint paper with Cris Moore, which eventually turned into this joint paper (ITCS '18) additionally with Dieter van Melkebeek and Andrew Morgan.