Joshua Grochow

Joshua A. Grochow is an assistant professor of computer science and mathematics at CU Boulder. His work focuses on two deeply - but not obviously - related themes:

• understanding the ultimate limits of computation (computational complexity), especially in their two-way relationship with algebraic geometry, representation theory, and group theory, and
• developing the theory of complex systems and complex networks.

Prior to his current position, he was an Omidyar Fellow at the Santa Fe Institute and a postdoc in the CS Theory group at the University of Toronto. He got his PhD in CS from the University of Chicago, an MEng in CS focusing on computational biology from the Massachusetts Institute of Technology, and undergraduate degrees in CS and mathematics from MIT.

Select Publications

• Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. With T. Pitassi. Journal of the ACM, 65(6), Article No. 37, November 2018. Preliminary version in FOCS '14.
• Unifying known lower bounds via geometric complexity theory. Computational Complexity, Special Issue, 24(2):393-475, 2015. Preliminary version in CCC '14.
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. With Y. Qiao. SIAM J. Comput., 52(2):568-617, 2023. Preliminary version appeared at ITCS '21, preprint arXiv '19.
• On cap sets and the group-theoretic approach to matrix multiplication. With J. Blasiak, T. Church, H. Cohn, E. Naslund, W. Sawin, and C. Umans. Discrete Analysis 2017:3.
• Towards an algebraic natural proofs barrier via polynomial identity testing. With M. Kumar, M. Saks, and S. Saraf. arXiv:1701.01717 [cs.CC, math.AG], 2017.
• Designing Strassen's algorithm. With C. Moore. arXiv:1708.09398 [cs.DS, cs.CC, cs.SC, math.RT], 2017.
• Monotone projection lower bounds from extended formulation lower bounds. Theory of Computing 13:18, 2017.
• On the Constant-Depth Circuit Complexity of Generating Quasigroups. With N. A. Collins, M. Levet, A. Weiß. arXiv:2402.00133 [cs.CC, cs.DS, math.CO, math.GR], 2024.

Video: Grochow's talks starts at 36:20.