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):
- Interactions between theoretical computer science and mathematics (particularly algebraic geometry, representation theory, and group theory), and
- 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!
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
(Jul 21, 2023) Maya Ornstein (co-advised by myself and Keith Kearnes) successfully defended her PhD thesis. Congratulations Maya!
(Jul 18, 2023) Paper accepted to FCT 2023: "On the parallel complexity of Group Isomorphism via Weisfeiler-Leman", joint with Michael Levet!
(Jun 29, 2023) Tzu-Chi Yen (co-advised by myself and Dan Larremore) successfully defended his PhD thesis. Congratulations Tzu-Chi!
(Jun 29, 2023) New preprint posted: On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications, joint with Y. Qiao!
(Jun 23, 2023) Quoted in a lovely Quanta Magazine article "Computer Scientists Inch Closer to Major Algorithmic Goal" by Kevin Hartnett on Xiaorui Sun's recent breakthrough (also on arXiv) on p-Group Isomorphism. I hope this article helps bring some visibility to these exciting developments!
(Jun 6, 2023) New preprint posted: On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups, joint with Z. Chen, Y. Qiao, G. Tang, and C. Zhang.
(Jun 5, 2023) New preprint posted: 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.
(May 31, 2023) Any day now has arrived. Preprint of our forthcoming CCC '23 paper posted: "On the algebraic proof complexity of Tensor Isomorphism", joint with Nicola Galesi, Toniann Pitassi and Adrian She.
(May 11-13, 2023) My PhD students Michael Levet, Maya Ornstein, and Tzu-Chi Yen 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!
(May 10, 2023) Paper accepted to CCC 2023: "On the algebraic proof complexity of Tensor Isomorphism", joint with Nicola Galesi, Toniann Pitassi and Adrian She. Preprint to be posted any day now...
(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.
(May 4, 2023) Guest blog post with Youming Qiao on the Computational Complexity Blog: Breaking Ground in Isomorphism Testing: A Leap Forward for a Bottleneck Case of Group Isomorphism.
(Apr 26, 2023) The final journal version of On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, joint with Youming Qiao has now appeared in SIAM J. Comput.!
(Apr 24, 2023) Gave a talk at the HyperMatrix Workshop, entitled "Equivalences between different kinds of objects represented by hyper-matrices". Join us this week!
(Mar 28, 2023) Gave a talk at ToniCS: Celebrating the Contributions and Influence of Toniann Pitassi, Working with Toni in Algebraic Proof Complexity.
(Mar 27, 2023) Chris Umans presented at WACT on our ITCS paper Matrix multiplication via matrix groups, joint with Jonah Blasiak, Henry Cohn, and Kevin Pratt.
(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 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