CINXE.COM

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"><head> <link rel="canonical" href="http://www.cs.colorado.edu/~jgrochow/index.html"> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <meta name="author" content="Joshua A. Grochow"> <meta name="description" content="Personal homepage of Joshua A. Grochow"> <meta name="robots" content="all"> <title>Joshua A. Grochow</title>  <script type="text/javascript"></script> <style type="text/css" media="all"> @import "main.css"; </style> </head> <body> <div class="header"> <table cellspacing="0" cellpadding="0" border="0"> <tbody><tr> <td valign="top"><img src="headshot.jpg" alt="Picture of Joshua A. Grochow" width="320px"></td> <td style="padding-left:20px;" width="100%"> <table> <tbody><tr> <td colspan="2"> <strong style="font-size:1.4em;">Joshua A. Grochow</strong> </td> </tr> <tr> <td style="width:500px" valign="top"> Associate Professor<br> Departments of Computer Science and Mathematics<br> University of Colorado at Boulder <br> [first initial][last name]@colorado.edu<br> I will not be in the office during the coronavirus pandemic. My virtual office is <a href="https://cuboulder.zoom.us/my/joshuagrochow">here on Zoom</a>. <br>  Fax: (303) 492-2844 (ATTN: me)<br> <a href="http://www.colorado.edu/cs-theory/">CS Theory @ CU Boulder</a><br> <a href="https://www.colorado.edu/cs/research/complex-systems">Complex Systems @ CU Boulder</a><br> <br> </td> <td valign="top">  </td> </tr> <tr> <td colspan="2"> Me @ <a href="https://bsky.app/profile/joshuagrochow.bsky.social">BlueSky</a> <a rel="me" href="https://mathstodon.xyz/@joshuagrochow">Mastodon</a> <a href="https://twitter.com/joshuagrochow">Twitter</a> <a href="http://cstheory.stackexchange.com/users/129/joshua-grochow">csthoery.SE</a> <a href="http://mathoverflow.net/users/38434/joshua-grochow">mathoverflow</a> <a href="http://orcid.org/0000-0002-6466-0476">ORCID</a> <br> My pubs @ <a href="http://arxiv.org/a/grochow_j_1.html">arXiv</a> <a href="http://eccc.hpi-web.de/author/188/">ECCC</a> <a href="http://dblp.uni-trier.de/pers/hd/g/Grochow:Joshua_A=">DBLP</a> <a href="http://www.ams.org/mathscinet/search/publications.html?pg1=INDI&s1=930146">MathSciNet</a> <a href="http://scholar.google.com/citations?user=CigslP0AAAAJ&hl=en">Google Scholar</a> <a href="http://scirate.com/joshua-grochow/papers">SciRate</a> </td> </tr> </tbody></table> </td> </tr> </tbody></table> </div> <div class="toc"> <ul id="navlist"> <li>About Me</li> <li><a href="research.html">Research</a></li> <li><a href="pubs.html">Publications</a></li> <li><a href="videos.html">Videos</a></li> <li><a href="mentoring.html">Mentoring</a></li> <li><a href="teaching.html">Teaching</a></li> <li><a href="resume.html">Resume</a></li> </ul> </div> <div class="content"> <h2 class="top">About Me</h2> <div style="overflow:auto;width:75%"> <p> I am an Associate Professor in the Departments of <a href="http://www.colorado.edu/cs">Computer Science</a> and <a href="http://www.colorado.edu/math/">Mathematics</a> at the <a href="">University of Colorado at Boulder</a>, where I am a member of the <a href="http://www.colorado.edu/cs-theory/">CS Theory Group</a> and the <a href="https://www.colorado.edu/cs/research/complex-systems">Complex Systems Group</a>. My research has two main thrusts (with deep underlying relations beneath): </p><ul> <li> Interactions between theoretical computer science and mathematics (particularly algebraic geometry, representation theory, and group theory), and </li> <li> Developing the theory of complex systems and complex networks, and applying this theory with my collaborators in a variety of fields, such as ecology, evolutionary biology, economics, climate, and beyond. I'm always looking for new problems that need new theory! </li> </ul> For a taste of the deep underlying relations, check out <a href="https://www.complexityexplorer.org/courses/58-introduction-to-computation-theory/segments/5908">this brief video</a>. <p></p> <p> I was previously an Omidyar Fellow at the interdisciplinary <a href="http://www.santafe.edu/">Santa Fe Institute</a> for complex systems. Prior to SFI, I was a postdoc in the <a href="http://www.cs.toronto.edu/theory/">University of Toronto CS Theory Group</a>, and prior to that I got my Ph.D. at the <a href="http://cs.uchicago.edu/">University of Chicago</a>. </p>  </div> <h2>What's new</h2> <div style="overflow:auto;width:75%"> <div style="overflow:auto"> (Nov 5, 2024) New preprint posted and accepted to ITCS '25: <a href="https://arxiv.org/abs/2410.14905">Finite matrix multiplication algorithms from infinite groups</a>, joint with <a href="http://www.math.drexel.edu/~jblasiak/">Jonah Blasiak</a>, <a href="http://research.microsoft.com/en-us/um/people/cohn/">Henry Cohn</a>, <a href="https://www.cs.cmu.edu/~kpratt/">Kevin Pratt</a>, and <a href="http://users.cms.caltech.edu/~umans/">Chris Umans</a>.<br /> <br /> (Oct 25, 2024) Presented at IU Bloomington's CS Colloquium, <a href="https://events.iu.edu/siceiub/event/1663944-tensors-everywhere-in-complexity">Tensors everywhere in complexity</a>.<br /> <br /> (Sep 30, 2024) Hiring a master's student researcher to work with me part-time on representation-theoretic and proof complexity approaches to Graph Isomorphism. Up to 15 hours/week, $16/hour. Bachelor's degree required, along with coursework in algebraic geometry, representation theory, and computational complexity. At most one of algebraic geometry or representation theory can be taken as a course concurrently with the research project. Dates TBD, can start ASAP, minimum of 6 months. <br /> <br /> (Summer 2024) Once again working with a great group of mentees this summer! A post-bacc researcher (Lucy Pipkorn) and 4 PhD students (Robby Green, Elise Tate, <a href="https://gulcekardes.owlstown.net/">Gülce Karde&scedil;</a>, and Nathaniel Collins from CSU). <br /> <br /> (Jun 20, 2024) Tenured!<br/> <br/> (May 5, 2024) Promoted to Associate Professor!<br /> <br /> (Apr 23, 2024) Paper accepted to <a href="">ISSAC 2024</a>! <a href="https://doi.org/10.1145/3666000.3669691">"On the Constant-Depth Circuit Complexity of Generating Quasigroups"</a>, joint with <a href="https://mathematics.colostate.edu/person/?id=AB4CDDACFFE0176CBE2DCD5160D443B1&sq=t">N. A. Collins</a>, <a href="https://michaellevet.github.io/">M. Levet</a>, <a href="https://scholar.google.com/citations?user=JQ3wCjwAAAAJ&hl=de">A. Weiß</a>. Preprint of full version available <a href="https://arxiv.org/abs/2402.00133">on the arXiv</a>.<br /> <br /> (Apr 16, 2024) Paper accepted to <a href="https://tqc-conference.org/">TQC 2024</a>! "Multipartite to tripartite reductions for LU and SLOCC equivalence", joint with Z. Chen, <a href="http://www.uts.edu.au/staff/youming.qiao">Y. Qiao</a>, G. Tang, and C. Zhang. The conference is hybrid in September 2024 - come join!<br /> <br /> (Feb 2024) Quoted in a great Communications of the ACM article "<a href="https://doi.org/10.1145/3637207">Algorithmic Advance: The Group Isomorphism Problem</a>" by <a href="https://ericaklarreich.pressfolios.com/">Erica Klarreich</a> on <a href="https://www.cs.uic.edu/~xiaorui/">Xiaorui Sun</a>'s <a href="https://doi.org/10.1145/3564246.3585250">recent breakthrough</a> (also <a href="https://arxiv.org/abs/2303.15412">on arXiv</a>) on p-Group Isomorphism. Also a nice mention at the end of our recent work with <a href="http://www.uts.edu.au/staff/youming.qiao">Youming Qiao</a>: "<a href="https://arxiv.org/abs/2306.16317">On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications</a>". I hope this article helps bring some visibility to these exciting developments!<br /> <br /> (Spring 2024) Ran a reading group <a href="https://git.cutheory.dev/joshuagrochow/s24-logiccomplexity">Machine-independent complexity and formalization in theorem-provers</a>. We are open to participants with the right prereqs (see page for details) and legitimate interest from anywhere. We currently have participants from CU Boulder (both Theory and PLV), U. Maryland, ENS France, UIUC, and BITS Pilani. Get in touch if you're interested in joining!<br /> <br /> (Jan 31, 2024) New preprint posted! <a href="https://arxiv.org/abs/2402.00133">On the Constant-Depth Circuit Complexity of Generating Quasigroups</a>, joint with <a href="https://mathematics.colostate.edu/person/?id=AB4CDDACFFE0176CBE2DCD5160D443B1&sq=t">N. A. Collins</a>, <a href="https://michaellevet.github.io/">M. Levet</a>, <a href="https://scholar.google.com/citations?user=JQ3wCjwAAAAJ&hl=de">A. Weiß</a>.<br /> <br /> (Nov 8, 2023) Paper accepted to ITCS '24: <a href="https://arxiv.org/abs/2306.03135">On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups</a>, joint with Z. Chen, <a href="http://www.uts.edu.au/staff/youming.qiao">Y. Qiao</a>, G. Tang, and C. Zhang.<br /> <br /> (Nov 2, 2023) Paper invited from GandALF '23 to special issue of <a href="https://lmcs.episciences.org/">Logical Methods in Computer Science</a>: <a href="https://arxiv.org/abs/2209.13725">On the Descriptive Complexity of Groups without Abelian Normal Subgroups</a>. joint with <a href="https://michaellevet.github.io/">Michael Levet</a>.<br /> <br /> (Aug 25, 2023) Paper accepted to <a href="https://gandalf23.uniud.it/">GandALF 2023</a>! "<a href="https://arxiv.org/abs/2310.01007v1">On the Descriptive Complexity of Groups without Abelian Normal Subgroups</a>" (<a href="https://arxiv.org/abs/2209.13725">full version here</a>) joint with <a href="https://michaellevet.github.io/">Michael Levet</a>.<br /> <br /> (Aug 1, 2023) Best Paper Award at <a href="https://www.uni-trier.de/en/universitaet/fachbereiche-faecher/fachbereich-iv/faecher/informatikwissenschaften/professuren/theoretische-informatik/research/conferences-and-workshops/fct-2023">FCT 2023</a> for our paper "<a href="https://doi.org/10.1007/978-3-031-43587-4_17">On the parallel complexity of Group Isomorphism via Weisfeiler-Leman</a>" (<a href="https://arxiv.org/abs/2112.11487">arXiv of full version</a>), joint with <a href="https://michaellevet.github.io/">Michael Levet</a>!<br /> <br /> <div style="overflow:auto"> <a href="https://uni-kassel.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=6853201f-0661-4002-9a5c-b04d00c5ce22"> <img src="levet highlights talk.png" width="280" height="157" style="float:left" /></a> <p style="width:50%;float:left;margin-top:0;padding-left:1em"> (Jul 28, 2023) <a href="https://michaellevet.github.io/">Michael Levet</a> presented hybrid online/in-person at <a href="https://highlights-conference.org/2023/">Highlights of Logic, Games, and Automata '23</a> on our GandALF '23' paper <a href="https://arxiv.org/abs/2209.13725">On the descriptive complexity of groups without Abelian normal subgroups</a>. </p> </div> <br /> <br /> (Jul 21, 2023) Maya Ornstein (co-advised by myself and <a href="https://math.colorado.edu/~kearnes/Home.html">Keith Kearnes</a>) successfully defended her PhD thesis. Congratulations Maya!<br /> <br /> (Jul 18, 2023) Paper accepted to <a href="https://www.uni-trier.de/en/universitaet/fachbereiche-faecher/fachbereich-iv/faecher/informatikwissenschaften/professuren/theoretische-informatik/research/conferences-and-workshops/fct-2023">FCT 2023</a>: "<a href="https://arxiv.org/abs/2112.11487">On the parallel complexity of Group Isomorphism via Weisfeiler-Leman</a>", joint with <a href="https://michaellevet.github.io/">Michael Levet</a>!<br /> <br /> (Jun 29, 2023) <a href="https://junipertcy.info/">Tzu-Chi Yen</a> (co-advised by myself and <a href="https://larremorelab.github.io/">Dan Larremore</a>) successfully defended his PhD thesis. Congratulations Tzu-Chi!<br /> <br /> (Jun 29, 2023) New preprint posted: <a href="https://arxiv.org/abs/2306.16317">On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications</a>, joint with <a href="http://www.uts.edu.au/staff/youming.qiao">Y. Qiao</a>!<br /> <br /> (Jun 23, 2023) Quoted in a lovely Quanta Magazine article "<a href="https://www.quantamagazine.org/computer-scientists-inch-closer-to-major-algorithmic-goal-20230623/">Computer Scientists Inch Closer to Major Algorithmic Goal</a>" by <a href="https://www.quantamagazine.org/authors/kevin-hartnett/">Kevin Hartnett</a> on <a href="https://www.cs.uic.edu/~xiaorui/">Xiaorui Sun</a>'s <a href="https://doi.org/10.1145/3564246.3585250">recent breakthrough</a> (also <a href="https://arxiv.org/abs/2303.15412">on arXiv</a>) on p-Group Isomorphism. I hope this article helps bring some visibility to these exciting developments!<br /> <br /> (Jun 6, 2023) New preprint posted: <a href="https://arxiv.org/abs/2306.03135">On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups</a>, joint with Z. Chen, <a href="http://www.uts.edu.au/staff/youming.qiao">Y. Qiao</a>, G. Tang, and C. Zhang.<br /> <br /> (Jun 5, 2023) New preprint posted: <a href="https://arxiv.org/abs/2306.02184">Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system</a>.<br /> <br /> (May 31, 2023) Any day now has arrived. Preprint of our forthcoming CCC '23 paper posted: "<a href="https://arxiv.org/abs/2305.19320">On the algebraic proof complexity of Tensor Isomorphism</a>", joint with <a href="https://sites.google.com/diag.uniroma1.it/nicolagalesi">Nicola Galesi</a>, <a href="https://www.cs.columbia.edu/~toni/">Toniann Pitassi</a> and <a href="http://www.cs.toronto.edu/~ashe/">Adrian She</a>.<br /> <br /> (May 11-13, 2023) My PhD students <a href="https://michaellevet.github.io/">Michael Levet</a>, <a href="https://www.colorado.edu/math/maya-ornstein">Maya Ornstein</a>, and <a href="https://junipertcy.info/">Tzu-Chi Yen</a> received their doctoral hoods, and undergraduate Nate Collins graduated summa cum laude, with the honors based in part on his thesis under myself and Michael. Congratulations Michael, Maya, Tzu-Chi, and Nate!<br /> <br /> (May 10, 2023) Paper accepted to <a href="https://computationalcomplexity.org/Archive/2023/accept.php">CCC 2023</a>: "<a href="https://arxiv.org/abs/2305.19320">On the algebraic proof complexity of Tensor Isomorphism</a>", joint with <a href="https://sites.google.com/diag.uniroma1.it/nicolagalesi">Nicola Galesi</a>, <a href="https://www.cs.columbia.edu/~toni/">Toniann Pitassi</a> and <a href="http://www.cs.toronto.edu/~ashe/">Adrian She</a>. Preprint to be posted any day now...<br /> <br /> (May 5, 2023) Temporary research assistant job opportunity (at the postdoctoral level) for June-July 2023. Duties include working with me and/or my students on mutually agreed upon research project(s) related to higher-order interactions and isomorphism testing. Pay is $32.50/hr. Apply by emailing me directly with CV/resume and transcript (unofficial is fine), as well as some indication of your relevant research experience and interests.<br /> <br /> (May 4, 2023) Guest blog post with <a href="http://www.uts.edu.au/staff/youming.qiao">Youming Qiao </a>on the Computational Complexity Blog: <a href="https://blog.computationalcomplexity.org/2023/05/breaking-ground-in-isomorphism-testing.html">Breaking Ground in Isomorphism Testing: A Leap Forward for a Bottleneck Case of Group Isomorphism</a>.<br /> <br /> (Apr 26, 2023) The final journal version of <a href="https://epubs.siam.org/eprint/VA7M2DT6DFQMVDVWIBBN/full">On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness</a>, joint with <a href="http://www.uts.edu.au/staff/youming.qiao">Youming Qiao</a> has now appeared in SIAM J. Comput.!<br /> <br /> <iframe width="280" height="157" src="https://www.youtube.com/embed/E8s9Daqy_2A" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen style="float:left"></iframe> <p style="width:50%;float:left;margin-top:0;padding-left:1em"> (Apr 24, 2023) Gave a talk at the <a href="https://arity.science/hypermatrixworkshop/">HyperMatrix Workshop</a>, entitled "Equivalences between different kinds of objects represented by hyper-matrices". Join us this week! </p> </div> <br /> <br /> <div style="overflow:auto"> <iframe width="280" height="157" src="https://www.youtube.com/embed/aai0TS2xcXE" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen style="float:left"></iframe> <p style="width:50%;float:left;margin-top:0;padding-left:1em"> (Mar 28, 2023) Gave a talk at <a href="https://simons.berkeley.edu/workshops/tonics-celebrating-contributions-influence-toniann-pitassi">ToniCS: Celebrating the Contributions and Influence of Toniann Pitassi</a>, <a href="https://simons.berkeley.edu/talks/josh-grochow-university-colorado-boulder-presenting-virtually-2023-03-28">Working with Toni in Algebraic Proof Complexity</a>. </p> </div> <br /> <br /> <div style="overflow:auto"> <a href="https://echo360.org.uk/media/a5a3fab4-ec63-4dc0-89d5-62b39041b7f6/public"> <img src="umans mat mul WACT talk.png" width="280" height="157" style="float:left" /></a> <p style="width:50%;float:left;margin-top:0;padding-left:1em"> (Mar 27, 2023) <a href="http://users.cms.caltech.edu/~umans/">Chris Umans</a> presented at <a href="https://www.dcs.warwick.ac.uk/~u2270030/wact/">WACT</a> on our ITCS paper <a href="https://arxiv.org/abs/2204.03826">Matrix multiplication via matrix groups</a>, joint with <a href="http://www.math.drexel.edu/~jblasiak/">Jonah Blasiak</a>, <a href="http://research.microsoft.com/en-us/um/people/cohn/">Henry Cohn</a>, and <a href="https://www.cs.cmu.edu/~kpratt/">Kevin Pratt</a>. </p> </div> <br /> <br /> (Mar 22, 2023) My student <a href="https://michaellevet.github.io/">Michael Levet</a> successfully defended his PhD thesis. Congratulations Michael!<br /> <br /> (Mar 16, 2023) Guest blog post on the Computational Complexity Blog: <a href="https://blog.computationalcomplexity.org/2023/03/identities-in-computational-complexity.html">Identities in Computational Complexity</a>.<br /> <br /> <div style="overflow:auto"> <iframe width="280" height="158" src="https://www.youtube.com/embed/xoM4nm_I8FM" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen style="float:left"></iframe> <p style="width:50%;float:left;margin-top:0;padding-left:1em"> (Jan 11, 2023) <a href="https://www.cs.cmu.edu/~kpratt/">Kevin Pratt</a> presented at ITCS on our paper <a href="https://arxiv.org/abs/2204.03826">Matrix multiplication via matrix groups</a>, joint with <a href="http://www.math.drexel.edu/~jblasiak/">Jonah Blasiak</a>, <a href="http://research.microsoft.com/en-us/um/people/cohn/">Henry Cohn</a>, and <a href="http://users.cms.caltech.edu/~umans/">Chris Umans</a>. </p> </div> <br /> <br /> <a href="updates.html">See all past updates</a> </div>  <script type="text/javascript"> var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www."); document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E")); </script><script src="ga.js" type="text/javascript"></script> <script type="text/javascript"> var pageTracker = _gat._getTracker("UA-3995595-1"); pageTracker._initData(); pageTracker._trackPageview(); </script>  </div></body></html>