Updates
(Nov 5, 2024) New preprint posted and accepted to ITCS '25: Finite matrix multiplication algorithms from infinite groups,
joint with Jonah Blasiak, Henry Cohn, Kevin Pratt, and Chris Umans.
(Oct 25, 2024) Presented at IU Bloomington's CS Colloquium, Tensors everywhere in complexity.
(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.
(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, Gülce Kardeş, and Nathaniel Collins from CSU).
(Jun 20, 2024) Tenured!
(May 5, 2024) Promoted to Associate Professor!
(Apr 23, 2024) Paper accepted to ISSAC 2024! "On the Constant-Depth Circuit Complexity of Generating Quasigroups", joint with N. A. Collins, M. Levet, A. Weiß. Preprint of full version available on the arXiv.
(Apr 16, 2024) Paper accepted to TQC 2024! "Multipartite to tripartite reductions for LU and SLOCC equivalence", joint with Z. Chen, Y. Qiao, G. Tang, and C. Zhang. The conference is hybrid in September 2024 - come join!
(Feb 2024) Quoted in a great Communications of the ACM article "Algorithmic Advance: The Group Isomorphism Problem" by Erica Klarreich on Xiaorui Sun's recent breakthrough (also on arXiv) on p-Group Isomorphism. Also a nice mention at the end of our recent work with Youming Qiao: "On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications". I hope this article helps bring some visibility to these exciting developments!
(Spring 2024) Ran a reading group Machine-independent complexity and formalization in theorem-provers. 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!
(Jan 31, 2024) New preprint posted! On the Constant-Depth Circuit Complexity of Generating Quasigroups, joint with N. A. Collins, M. Levet, A. Weiß.
(Nov 2, 2023) Paper invited from GandALF '23 to special issue of Logical Methods in Computer Science: On the Descriptive Complexity of Groups without Abelian Normal Subgroups. joint with Michael Levet.
(Aug 25, 2023) Paper accepted to GandALF 2023! "On the Descriptive Complexity of Groups without Abelian Normal Subgroups" (full version here) joint with Michael Levet.
(Aug 1, 2023) Best Paper Award at FCT 2023 for our paper "On the parallel complexity of Group Isomorphism via Weisfeiler-Leman" (arXiv of full version), joint with Michael Levet!
(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.!
(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.
(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) 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.
(November 29-December 3, 2021) Participated in the Simons Institute Workshop Optimization under Symmetry.
(November 9-12, 2021) Gave two talks in the School and Conference on Geometric Complexity Theory:
(Fall 2021) Teaching graduate-level Computational Complexity and undergraduate Algorithms. Trying out ungrading for the first time in the grad class. For the undergrad class I think we finally have mastery- and standards-based grading working really well in this course!
(Aug 19, 2021) Our joint work on Tensor Isomorphism-completeness with Y. Qiao was highlighted, and I was quoted several times, in a Quanta article by Stephen Ornes about higher-order interactions.
(Summer 2021) Working with a great group of students and postdocs! Two undergraduates (Nicole Dong, Ezzeddine El Sai), 6 graduate students (Gabriel Andrade, Robby Green, Michael Levet, Joel Ornstein, Elise Tate, Tzu-Chi Yen), and 2 postdocs Nathan Lindzey, Abhiram Natarajan).
(Mar 8 - Jun 11, 2021) IPAM Fellow at the IPAM Long Program on "Tensor Methods and Emerging Applications to the Physical and Data Sciences".
(May 25, 2021) Gave a talk in the IPAM Long Program on "Tensor Methods and Emerging Applications to the Physical and Data Sciences", "Tensor Isomorphism in its various incarnations", based on this paper joint with Vyacheslav Futorny and Vladimir V. Sergeichuk and this preprint (appeared at ITCS '21), with Youming Qiao.
(May 10, 2021) "On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors" accepted to CCC '21! Joint with Youming Qiao, based on part of this preprint.
(Apr 30, 2021) Honorable mention for the CU Boulder CS Graduate Student Advising Award.
(Apr 28, 2021) Gave a talk in the TU Berlin Kolloquium on on Algorithmic Mathematics & Complexity, based on a part of this preprint (appeared at ITCS '21), with Youming Qiao.
(Jan 6-8, 2021) Gave a talk (watch the video, shorter live version with Q&A) at ITCS '21 on "On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness". This is part of this preprint, with Youming Qiao.
(Dec 2, 2020) New preprint posted, Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms with Youming Qiao and Gang Tang.
(Nov 24, 2020) Gave a talk in the LA Combinatorics & Complexity Seminar, "Designing Strassen's algorithm for matrix multiplication", based on this paper joint with Cris Moore. Watch the video here!
(Nov 17, 2020) Paper accepted to ITCS '21! "On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness." This is part of this preprint, with Youming Qiao.
(Oct 28, 2020) Gave a talk in the Johns Hopkins CS Theory Seminar, "Isomorphism of tensors, algebras, and polynomials, oh my!", based on these three papers.
(Sep 24, 2020) Gave a (virtual) talk at the Clarkson University Center for Complex Systems Science (C3S2), "Understanding large systems from their small parts: Algorithms & theory".
(Sep 10, 2020) Gave a (virtual) talk in our CS Colloquium: "Can we understand big systems from their small parts?", based in part on these three papers.
(Summer 2020) I worked with a great group of students and postdocs this summer! Two high school students (Michael Klyachman, Yerim Song), four undergraduates (Nicole Dong, Ezzeddine El Sai, Sam Serra, Tarek Tohme), 5 graduate students (Gabriel Andrade, Robby Green, Michael Levet, Joel Ornstein, Tzu-Chi Yen), and 3 postdocs Nathan Lindzey, Abhiram Natarajan, Eric Reckwerdt). Crazy but fun - keep an eye out of the results from some of these collaborations!
(Apr 18, 2020) New survey published, in Bull. EATCS, with lots of open questions! Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs.
(Spring 2020) Implemented standards-based grading at scale (~300 students) in CSCI 3104 Intro Algorithms, along with Lijun Chen, and a talented team of graduate TAs and undergraduate course assistants.
(Oct 22, 2019) Dynamics of Beneficial Epidemics appeared in Nature Scientific Reports—the final (?) outcome of the first SFI 72 Hours of Science!
(Aug-Dec, 2019) Developed & ran a new course, Practical Algorithmic Complexity.
(Jul 12, 2019) Gave a talk on Tensor Isomorphism: completeness, graph-theoretic methods, and consequences for Group Isomorphism—watch the talk here—at the Banff International Research Station Workshop on Algebraic Techniques in Computational Complexity. Based on these three papers.
(Jul 1, 2019) New preprint posted! Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions, joint with Youming Qiao.
(May 20, 2019) My first ever ecology paper (or, at least, one to which I contributed in some small way): Ecogeographical rules and the macroecology of food webs. With a ton of great people: B. Baiser, D. Gravel, A. R. Cirtwell, J. A. Dunne, A. K. Fahimipour, L. J. Gilarranz, D. Li, N. D. Martinez, A. McGrew, T. N. Romanuk, D. B. Stouffer, L. B. Trotta, F. S. Valdovinos, R. J. Williams, S. A. Wood, and J. D. Yeakel.
(May 6, 2019) New preprint posted: Incorporating Weisfeiler-Leman into algorithms for group isomorphism, joint with Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson.
(Oct 22, 2018) New paper posted online: Wildness for tensors! Joint with Vyacheslav Futorny and Vladimir V. Sergeichuk.
(Oct 1, 2018) New expository paper published in the Bulletin of the AMS: New applications of the polynomial method: the cap set conjecture and beyond!
(July 23-26, 2018) Invited speaker at the Clay Math Institute/Oxford Workshop on Complexity Theory! I spoke on "Complexity in Ideals of Polynomials." Student support available.
(July 23, 2018) Report from the January Dagstuhl Workshop on Proof Complexity now available, including lots of great open questions!
(June 18, 2018) New paper published with David H. Wolpert: Beyond number of bit erasures: New complexity questions raised by recently discovered thermodynamic costs of computation in SIGACT News! Feedback more than welcome.
(June 14, 2018) My co-author Jamie Tucker-Foltz presented @ SoCG 2018 on our joint paper "Computational topology and the Unique Games Conjecture."
(June 1, 2018) The Ideal Proof System accepted to J. ACM! (To appear.)
(June 1, 2018) I'm happy to announce that Alex Kolla and I have hired Eric Reckwerdt and Nathan Lindzey as our postdocs! They'll be starting Fall '18 and Jan '19, respectively.
(May 1, 2018) Gave a talk in the Topology Seminar in the CU Math Department on Computational topology and the Unique Games Conjecture.
(Mar 20, 2018) New paper posted: "Computational topology and the Unique Games Conjecture", to appear at SoCG 2018. Joint with Jamie Tucker-Foltz.
(Mar 19, 2018) Minimum circuit size, graph isomorphism, and related problems accepted to SIAM J. Comput.! Joint with Eric Allender, Dieter van Melkebeek, Cris Moore, and Andrew Morgan.
(Mar 16, 2018) Gave a talk in the CU Boulder Applied Math Colloquium: "Computational Complexity, Dynamical Systems, and Non-Convex Optimization."
(Mar 2, 2018) Gave a talk at the Rocky Mountain Algebraic Combinatorics Seminar: "Combinatorial Polytopes in Algebraic and Geometric Complexity Theory," based partially on these two papers.
(Feb 28, 2018) Presented "Computational Complexity and Mathematics" at the CU Boulder Math Club. With computer science, math, pizza, and drinks, how can you go wrong?
(Feb 16, 2018) "Computational topology and the Unique Games Conjecture" accepted to SoCG 2018. Joint with Jamie Tucker-Foltz.Preprint coming soon UPDATE 3/20/2018: now available!
(Due Jan 31, 2018) We solicited applications for a Postdoctoral Fellowship beginning 2018! Algebraic/geometric complexity, spectral algorithms, unique games, and more with me and Alex Kolla. Check out our theory group.
(Jan 31, 2018) Gave a talk on Ideal Proof Systems at this Dagstuhl Workshop on Proof Complexity. Update 7/23/2018: report now available.
(Jan 12, 2018) Gave an invited talk at the AMS Current Events Bulletin, "The Cap Set Conjecture, the polynomial method, and applications (after Croot-Lev-Pach, Ellenberg-Gijswijt, and others)." You can find a write-up associated with the talk in the 2018 Current Events Bulletin booklet. UPDATE Oct 1, 2018: Revised and expanded version published in Bulletin of the AMS!
(Due Dec 15, 2017) I was seeking Ph.D. students, in computational complexity and/or complex systems & networks.
(Dec 7, 2017) New paper posted: Which groups are amenable to proving exponent two for matrix multiplication? Joint with Jonah Blasiak, Thomas Church, Henry Cohn, and Chris Umans. In which, among other things, we give a nonabelian generalization of the Croot-Lev-Pach-Ellenberg-Gijswijt method.
(Dec 5, 2017) Speaking in the CU Boulder Math Lie Theory seminar: Representation theory and additive combinatorics in algorithms for matrix multiplication.
(Nov 14, 2017) Gave CU Boulder Kempner Colloquium in the Math Department: "Wildness & geometry in representation theory & computational complexity."
(Oct 23, 2017) New paper posted: Minimum circuit size, graph isomorphism, and related problems! Joint with Eric Allender, Dieter van Melkebeek, Cris Moore, and Andrew Morgan.
(Oct 6, 2017) Gave a talk at the Rocky Mountain Algebraic Combinatorics Seminar in Fort Collins: Representation theory and additive combinatorics in algorithms for matrix multiplication.
(Sep 1, 2017) New paper posted: Designing Strassen's algorithm, showing a clean proof of Strassen's algorithm using only a simple unitary 2-design in two dimensions. Joint with Cris Moore.
(Jul 7, 2017) The final, open access version of Algorithms for group isomorphism via group extensions and cohomology has now appeared in SIAM Journal on Computation! Joint with Youming Qiao. Open access forever thanks to funding from the Santa Fe Institute.
(Jun 30, 2017) I am now officially, by courtesy, also an Assistant Professor in the Department of Mathematics!
(Jun 23, 2017) Comparing information-theoretic measures of complexity in Boltzmann machines accepted to Entropy! Joint with my former REU student from SFI (now at Berkeley), Max Kanwal, and Nihat Ay.
(May 11, 2017) New paper posted: On the records, joint with the Santa Fe Institute postdocs. This paper was the result of our second (annual?) "72 Hours of Science" event, in which we conceived, developed, executed, and wrote up an entire scientific project in only 72 hours (albeit with a team of 15 postdocs)! See the Appendix of the paper for a little more detail. Comments and suggestions are more than welcome.
(Apr 18, 2017) On cap sets and the group-theoretic approach to matrix multiplication invited as a plenary talk at the STOC TheoryFest, which highlights some of the best CS theory work from any venue in the past two years!
(Apr 3, 2017) Algorithms for group isomorphism via group extensions and cohomology accepted to SIAM Journal on Computing! See the improved results and exposition due to the refereeing process in the updated arXiv version. Joint with Youming Qiao. To appear any day now...
(Jan 16, 2017) On cap sets and the group-theoretic approach to matrix multiplication accepted to Discrete Analysis. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, Eric Naslund, Will Sawin, and Chris Umans.
(Jan 8, 2017) New paper posted: Towards an algebraic natural proofs barrier via polynomial identity testing, joint with Mrinal Kumar, Mike Saks, and Shubhangi Saraf.
(Dec 15, 2016) Excited to be part of the FOCS 2017 program committee!
(Dec 6, 2016) New preprint posted: Matrix multiplication algorithms from group orbits, joint with Cris Moore.
(Dec 3, 2016) New paper posted: A quantitative definition of organismality and its application to lichen, led by Eric Libby, joint with Simon DeDeo and David Wolpert.
(Oct 24, 2016) Gave a talk at UT Austin: "Wildness at the heart of complexity."
(Oct 19, 2016) New paper posted: NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications.
(Oct 18, 2016) New CS Theory Group website launched for CU Boulder. Come join us!
(Aug 18, 2016) The onion decomposition accepted to Scientific Reports!
(Aug 15, 2016) Started as Assistant Professor at CU Boulder Computer Science! I'm officially on leave until Summer 2017, in order to finish my current postdoc. But I'm still looking for Ph.D. students to start in 2017, as well as other theory colleagues who might join us!
(Aug 10, 2016) Paper updated: On cap sets and the group-theoretic approach to matrix multiplication. Results extended from vector spaces over finite fields to arbitrary abelian groups of bounded exponent, and made a new connection to geometric invariant theory. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, Eric Naslund, Will Sawin, and Chris Umans.
(July 27, 2016) Monotone projection lower bounds from extended formulation lower bounds accepted to Theory of Computing, where it now enters the "print queue," awaiting (I think) copy editing.
(Oct 25, 2024) Presented at IU Bloomington's CS Colloquium, Tensors everywhere in complexity.
(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.
(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, Gülce Kardeş, and Nathaniel Collins from CSU).
(Jun 20, 2024) Tenured!
(May 5, 2024) Promoted to Associate Professor!
(Apr 23, 2024) Paper accepted to ISSAC 2024! "On the Constant-Depth Circuit Complexity of Generating Quasigroups", joint with N. A. Collins, M. Levet, A. Weiß. Preprint of full version available on the arXiv.
(Apr 16, 2024) Paper accepted to TQC 2024! "Multipartite to tripartite reductions for LU and SLOCC equivalence", joint with Z. Chen, Y. Qiao, G. Tang, and C. Zhang. The conference is hybrid in September 2024 - come join!
(Feb 2024) Quoted in a great Communications of the ACM article "Algorithmic Advance: The Group Isomorphism Problem" by Erica Klarreich on Xiaorui Sun's recent breakthrough (also on arXiv) on p-Group Isomorphism. Also a nice mention at the end of our recent work with Youming Qiao: "On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications". I hope this article helps bring some visibility to these exciting developments!
(Spring 2024) Ran a reading group Machine-independent complexity and formalization in theorem-provers. 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!
(Jan 31, 2024) New preprint posted! On the Constant-Depth Circuit Complexity of Generating Quasigroups, joint with N. A. Collins, M. Levet, A. Weiß.
2023 Updates
(Nov 8, 2023) Paper accepted to ITCS '24: 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.(Nov 2, 2023) Paper invited from GandALF '23 to special issue of Logical Methods in Computer Science: On the Descriptive Complexity of Groups without Abelian Normal Subgroups. joint with Michael Levet.
(Aug 25, 2023) Paper accepted to GandALF 2023! "On the Descriptive Complexity of Groups without Abelian Normal Subgroups" (full version here) joint with Michael Levet.
(Aug 1, 2023) Best Paper Award at FCT 2023 for our paper "On the parallel complexity of Group Isomorphism via Weisfeiler-Leman" (arXiv of full version), joint with Michael Levet!
(Jul 28, 2023) Michael Levet presented hybrid online/in-person at Highlights of Logic, Games, and Automata '23 on our GandALF '23' paper On the descriptive complexity of groups without Abelian normal subgroups.
(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 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.
2022 Updates
(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!).
2021 Updates
(Dec 22, 2021) My student Michael Levet and I just posted our new preprint, Weisfeiler-Leman for Group Isomorphism: Action Compatibility.(November 29-December 3, 2021) Participated in the Simons Institute Workshop Optimization under Symmetry.
(November 9-12, 2021) Gave two talks in the School and Conference on Geometric Complexity Theory:
- Representations in coordinate rings and partial stability in Geometric Complexity Theory
- Characterization by symmetries, natural proofs, and P vs NP in Geometric Complexity Theory
(Fall 2021) Teaching graduate-level Computational Complexity and undergraduate Algorithms. Trying out ungrading for the first time in the grad class. For the undergrad class I think we finally have mastery- and standards-based grading working really well in this course!
(Aug 19, 2021) Our joint work on Tensor Isomorphism-completeness with Y. Qiao was highlighted, and I was quoted several times, in a Quanta article by Stephen Ornes about higher-order interactions.
(July 20-22, 2021) Gave a talk at CCC '21 on On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors. Joint with Youming Qiao, based on part of this preprint.
(Summer 2021) Working with a great group of students and postdocs! Two undergraduates (Nicole Dong, Ezzeddine El Sai), 6 graduate students (Gabriel Andrade, Robby Green, Michael Levet, Joel Ornstein, Elise Tate, Tzu-Chi Yen), and 2 postdocs Nathan Lindzey, Abhiram Natarajan).
(Mar 8 - Jun 11, 2021) IPAM Fellow at the IPAM Long Program on "Tensor Methods and Emerging Applications to the Physical and Data Sciences".
(May 25, 2021) Gave a talk in the IPAM Long Program on "Tensor Methods and Emerging Applications to the Physical and Data Sciences", "Tensor Isomorphism in its various incarnations", based on this paper joint with Vyacheslav Futorny and Vladimir V. Sergeichuk and this preprint (appeared at ITCS '21), with Youming Qiao.
(May 10, 2021) "On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors" accepted to CCC '21! Joint with Youming Qiao, based on part of this preprint.
(Apr 30, 2021) Honorable mention for the CU Boulder CS Graduate Student Advising Award.
(Apr 28, 2021) Gave a talk in the TU Berlin Kolloquium on on Algorithmic Mathematics & Complexity, based on a part of this preprint (appeared at ITCS '21), with Youming Qiao.
(Feb 23, 2021) Gave a talk in the Codes and Expansions (CodEx) Seminar, Codes and Expansions in Algorithms for Matrix Multiplication.
(Jan 6-8, 2021) Gave a talk (watch the video, shorter live version with Q&A) at ITCS '21 on "On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness". This is part of this preprint, with Youming Qiao.
2020 Updates
(Dec 20, 2020) Paper accepted to STACS '21! Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms with Youming Qiao and Gang Tang.(Dec 2, 2020) New preprint posted, Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms with Youming Qiao and Gang Tang.
(Nov 24, 2020) Gave a talk in the LA Combinatorics & Complexity Seminar, "Designing Strassen's algorithm for matrix multiplication", based on this paper joint with Cris Moore. Watch the video here!
(Nov 17, 2020) Paper accepted to ITCS '21! "On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness." This is part of this preprint, with Youming Qiao.
(Oct 28, 2020) Gave a talk in the Johns Hopkins CS Theory Seminar, "Isomorphism of tensors, algebras, and polynomials, oh my!", based on these three papers.
(Sep 24, 2020) Gave a (virtual) talk at the Clarkson University Center for Complex Systems Science (C3S2), "Understanding large systems from their small parts: Algorithms & theory".
(Sep 10, 2020) Gave a (virtual) talk in our CS Colloquium: "Can we understand big systems from their small parts?", based in part on these three papers.
(Summer 2020) I worked with a great group of students and postdocs this summer! Two high school students (Michael Klyachman, Yerim Song), four undergraduates (Nicole Dong, Ezzeddine El Sai, Sam Serra, Tarek Tohme), 5 graduate students (Gabriel Andrade, Robby Green, Michael Levet, Joel Ornstein, Tzu-Chi Yen), and 3 postdocs Nathan Lindzey, Abhiram Natarajan, Eric Reckwerdt). Crazy but fun - keep an eye out of the results from some of these collaborations!
(Apr 18, 2020) New survey published, in Bull. EATCS, with lots of open questions! Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs.
(Spring 2020) Implemented standards-based grading at scale (~300 students) in CSCI 3104 Intro Algorithms, along with Lijun Chen, and a talented team of graduate TAs and undergraduate course assistants.
2019 Updates
(Dec 2019) My first Ph.D. student, Tyler Schrock, graduated - congratulations Tyler!(Oct 22, 2019) Dynamics of Beneficial Epidemics appeared in Nature Scientific Reports—the final (?) outcome of the first SFI 72 Hours of Science!
(Aug-Dec, 2019) Developed & ran a new course, Practical Algorithmic Complexity.
(Jul 12, 2019) Gave a talk on Tensor Isomorphism: completeness, graph-theoretic methods, and consequences for Group Isomorphism—watch the talk here—at the Banff International Research Station Workshop on Algebraic Techniques in Computational Complexity. Based on these three papers.
(Jul 1, 2019) New preprint posted! Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions, joint with Youming Qiao.
(May 20, 2019) My first ever ecology paper (or, at least, one to which I contributed in some small way): Ecogeographical rules and the macroecology of food webs. With a ton of great people: B. Baiser, D. Gravel, A. R. Cirtwell, J. A. Dunne, A. K. Fahimipour, L. J. Gilarranz, D. Li, N. D. Martinez, A. McGrew, T. N. Romanuk, D. B. Stouffer, L. B. Trotta, F. S. Valdovinos, R. J. Williams, S. A. Wood, and J. D. Yeakel.
(May 6, 2019) New preprint posted: Incorporating Weisfeiler-Leman into algorithms for group isomorphism, joint with Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson.
2018 Updates
(Dec 27, 2018) Wildness for tensors accepted to Linear Algebra and its Applications! Joint with Vyacheslav Futorny and Vladimir V. Sergeichuk.(Oct 22, 2018) New paper posted online: Wildness for tensors! Joint with Vyacheslav Futorny and Vladimir V. Sergeichuk.
(Oct 1, 2018) New expository paper published in the Bulletin of the AMS: New applications of the polynomial method: the cap set conjecture and beyond!
(July 23-26, 2018) Invited speaker at the Clay Math Institute/Oxford Workshop on Complexity Theory! I spoke on "Complexity in Ideals of Polynomials." Student support available.
(July 23, 2018) Report from the January Dagstuhl Workshop on Proof Complexity now available, including lots of great open questions!
(June 18, 2018) New paper published with David H. Wolpert: Beyond number of bit erasures: New complexity questions raised by recently discovered thermodynamic costs of computation in SIGACT News! Feedback more than welcome.
(June 14, 2018) My co-author Jamie Tucker-Foltz presented @ SoCG 2018 on our joint paper "Computational topology and the Unique Games Conjecture."
(June 1, 2018) The Ideal Proof System accepted to J. ACM! (To appear.)
(June 1, 2018) I'm happy to announce that Alex Kolla and I have hired Eric Reckwerdt and Nathan Lindzey as our postdocs! They'll be starting Fall '18 and Jan '19, respectively.
(May 1, 2018) Gave a talk in the Topology Seminar in the CU Math Department on Computational topology and the Unique Games Conjecture.
(Mar 20, 2018) New paper posted: "Computational topology and the Unique Games Conjecture", to appear at SoCG 2018. Joint with Jamie Tucker-Foltz.
(Mar 19, 2018) Minimum circuit size, graph isomorphism, and related problems accepted to SIAM J. Comput.! Joint with Eric Allender, Dieter van Melkebeek, Cris Moore, and Andrew Morgan.
(Mar 16, 2018) Gave a talk in the CU Boulder Applied Math Colloquium: "Computational Complexity, Dynamical Systems, and Non-Convex Optimization."
(Mar 2, 2018) Gave a talk at the Rocky Mountain Algebraic Combinatorics Seminar: "Combinatorial Polytopes in Algebraic and Geometric Complexity Theory," based partially on these two papers.
(Feb 28, 2018) Presented "Computational Complexity and Mathematics" at the CU Boulder Math Club. With computer science, math, pizza, and drinks, how can you go wrong?
(Feb 16, 2018) "Computational topology and the Unique Games Conjecture" accepted to SoCG 2018. Joint with Jamie Tucker-Foltz.
(Due Jan 31, 2018) We solicited applications for a Postdoctoral Fellowship beginning 2018! Algebraic/geometric complexity, spectral algorithms, unique games, and more with me and Alex Kolla. Check out our theory group.
(Jan 31, 2018) Gave a talk on Ideal Proof Systems at this Dagstuhl Workshop on Proof Complexity. Update 7/23/2018: report now available.
(Jan 12, 2018) Gave an invited talk at the AMS Current Events Bulletin, "The Cap Set Conjecture, the polynomial method, and applications (after Croot-Lev-Pach, Ellenberg-Gijswijt, and others)." You can find a write-up associated with the talk in the 2018 Current Events Bulletin booklet. UPDATE Oct 1, 2018: Revised and expanded version published in Bulletin of the AMS!
2017 Updates
(Dec 22, 2017) Monotone projection lower bounds from extended formulation lower bounds finally appeared in Theory of Computing.(Due Dec 15, 2017) I was seeking Ph.D. students, in computational complexity and/or complex systems & networks.
(Dec 7, 2017) New paper posted: Which groups are amenable to proving exponent two for matrix multiplication? Joint with Jonah Blasiak, Thomas Church, Henry Cohn, and Chris Umans. In which, among other things, we give a nonabelian generalization of the Croot-Lev-Pach-Ellenberg-Gijswijt method.
(Dec 5, 2017) Speaking in the CU Boulder Math Lie Theory seminar: Representation theory and additive combinatorics in algorithms for matrix multiplication.
(Nov 14, 2017) Gave CU Boulder Kempner Colloquium in the Math Department: "Wildness & geometry in representation theory & computational complexity."
(Oct 23, 2017) New paper posted: Minimum circuit size, graph isomorphism, and related problems! Joint with Eric Allender, Dieter van Melkebeek, Cris Moore, and Andrew Morgan.
(Oct 6, 2017) Gave a talk at the Rocky Mountain Algebraic Combinatorics Seminar in Fort Collins: Representation theory and additive combinatorics in algorithms for matrix multiplication.
(Sep 1, 2017) New paper posted: Designing Strassen's algorithm, showing a clean proof of Strassen's algorithm using only a simple unitary 2-design in two dimensions. Joint with Cris Moore.
(Jul 7, 2017) The final, open access version of Algorithms for group isomorphism via group extensions and cohomology has now appeared in SIAM Journal on Computation! Joint with Youming Qiao. Open access forever thanks to funding from the Santa Fe Institute.
(Jun 30, 2017) I am now officially, by courtesy, also an Assistant Professor in the Department of Mathematics!
(Jun 23, 2017) Comparing information-theoretic measures of complexity in Boltzmann machines accepted to Entropy! Joint with my former REU student from SFI (now at Berkeley), Max Kanwal, and Nihat Ay.
(May 11, 2017) New paper posted: On the records, joint with the Santa Fe Institute postdocs. This paper was the result of our second (annual?) "72 Hours of Science" event, in which we conceived, developed, executed, and wrote up an entire scientific project in only 72 hours (albeit with a team of 15 postdocs)! See the Appendix of the paper for a little more detail. Comments and suggestions are more than welcome.
(Apr 18, 2017) On cap sets and the group-theoretic approach to matrix multiplication invited as a plenary talk at the STOC TheoryFest, which highlights some of the best CS theory work from any venue in the past two years!
(Apr 3, 2017) Algorithms for group isomorphism via group extensions and cohomology accepted to SIAM Journal on Computing! See the improved results and exposition due to the refereeing process in the updated arXiv version. Joint with Youming Qiao. To appear any day now...
(Jan 16, 2017) On cap sets and the group-theoretic approach to matrix multiplication accepted to Discrete Analysis. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, Eric Naslund, Will Sawin, and Chris Umans.
(Jan 8, 2017) New paper posted: Towards an algebraic natural proofs barrier via polynomial identity testing, joint with Mrinal Kumar, Mike Saks, and Shubhangi Saraf.
2016 Updates
(Dec 31, 2016) Excited to be part of the NetSci 2017 program committee!(Dec 15, 2016) Excited to be part of the FOCS 2017 program committee!
(Dec 6, 2016) New preprint posted: Matrix multiplication algorithms from group orbits, joint with Cris Moore.
(Dec 3, 2016) New paper posted: A quantitative definition of organismality and its application to lichen, led by Eric Libby, joint with Simon DeDeo and David Wolpert.
(Oct 24, 2016) Gave a talk at UT Austin: "Wildness at the heart of complexity."
(Oct 19, 2016) New paper posted: NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications.
(Oct 18, 2016) New CS Theory Group website launched for CU Boulder. Come join us!
(Aug 18, 2016) The onion decomposition accepted to Scientific Reports!
(Aug 15, 2016) Started as Assistant Professor at CU Boulder Computer Science! I'm officially on leave until Summer 2017, in order to finish my current postdoc. But I'm still looking for Ph.D. students to start in 2017, as well as other theory colleagues who might join us!
(Aug 10, 2016) Paper updated: On cap sets and the group-theoretic approach to matrix multiplication. Results extended from vector spaces over finite fields to arbitrary abelian groups of bounded exponent, and made a new connection to geometric invariant theory. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, Eric Naslund, Will Sawin, and Chris Umans.
(July 27, 2016) Monotone projection lower bounds from extended formulation lower bounds accepted to Theory of Computing, where it now enters the "print queue," awaiting (I think) copy editing.
(May 29, 2016) Excited to be part of the CCC 2017 Program Committee!
(May 26, 2016) Gave a talk in the Philadelphia area Combinatorics and Algebraic Geometry (CAGE) seminar: "Newton polytopes of quiver semi-invariants in geometric complexity theory," on (part of) this paper.
(May 23, 2016) New paper posted: On cap sets and the group-theoretic approach to matrix multiplication. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, and Chris Umans.
(May 11, 2016) Full version of Boundaries of VP and VNP now available as an arXiv preprint.
(April 27, 2016) "Boundaries of VP and VNP" accepted to ICALP 2016! Joint with Ketan Mulmuley and Youming Qiao.
(April 12, 2016) Story by Jennifer Ouellette on Dynamics of beneficial epidemics, and how we produced it in just 72 Hours of Science.
(April 12, 2016) Gave a CS colloquium at CU Boulder: "What makes individual problem instances hard? Computational complexity and complex systems." You can watch the video here.
(April 7, 2016) New paper posted: Dynamics of beneficial epidemics, joint with the Santa Fe Institute postdocs. This paper was the result of our "72 Hours of Science" event, in which we conceived, developed, executed, and wrote up an entire scientific project in only 72 hours (albeit with a team of 14 postdocs)! See the Appendix of the paper for a little more detail. Comments and suggestions are more than welcome.
(March 29, 2016) Gave a talk at the UW CS Theory Seminar: Combinatorial polytopes in algebraic and geometric complexity theory, about this paper and a forthcoming paper with Ketan Mulmuley and Youming Qiao.
(November 3, 2015) Updated Monotone projection lower bounds from extended formulation lower bounds with new lower bound against reductions from perfect matchings in general graphs to perfect matchings in bipartite graphs.
(October 29, 2015) New paper posted: Network structure at multiple scales via a new network statistic: the onion decomposition, joint with Laurent Hébert-Dufresne and Antoine Allard.
(October 28, 2015) New paper posted: Monotone projection lower bounds from extended formulation lower bounds.
(October 12-16, 2015) Organized the SFI Workshop on Wildness in Computer Science, Physics, and Mathematics.
(October 8, 2015) New paper posted: Graph isomorphism and circuit size, joint with Eric Allender and Cris Moore.
(August 31, 2015) Polynomial-time isomorphism test of groups that are tame extensions accepted to ISAAC 2015 (the leading conference on algorithms in (East) Asia).
(July 14, 2015) You can listen to my interview by @Samuel_Hansen for the Strongly Connected Components podcast. My segment starts at 40:45, but you should also listen to the preceding interviews with my colleagues Yoav Kallus and Sid Redner!
(July 7, 2015) New paper posted: Polynomial-time isomorphism test of groups that are tame extensions (joint w/ Youming Qiao).
(May 9, 2015) The final, significantly expanded and edited version of Unifying known lower bounds via geometric complexity theory has now appeared in Computational Complexity, and is freely available forever (thanks to funding from SFI).
(Apr 21, 2015) Gave a CS colloquium at UNM: The role of symmetry (or the lack thereof) in algorithms and computational complexity.
(May 26, 2016) Gave a talk in the Philadelphia area Combinatorics and Algebraic Geometry (CAGE) seminar: "Newton polytopes of quiver semi-invariants in geometric complexity theory," on (part of) this paper.
(May 23, 2016) New paper posted: On cap sets and the group-theoretic approach to matrix multiplication. Joint with Jonah Blasiak, Thomas Church, Henry Cohn, and Chris Umans.
(May 11, 2016) Full version of Boundaries of VP and VNP now available as an arXiv preprint.
(April 27, 2016) "Boundaries of VP and VNP" accepted to ICALP 2016! Joint with Ketan Mulmuley and Youming Qiao.
(April 12, 2016) Story by Jennifer Ouellette on Dynamics of beneficial epidemics, and how we produced it in just 72 Hours of Science.
(April 12, 2016) Gave a CS colloquium at CU Boulder: "What makes individual problem instances hard? Computational complexity and complex systems." You can watch the video here.
(April 7, 2016) New paper posted: Dynamics of beneficial epidemics, joint with the Santa Fe Institute postdocs. This paper was the result of our "72 Hours of Science" event, in which we conceived, developed, executed, and wrote up an entire scientific project in only 72 hours (albeit with a team of 14 postdocs)! See the Appendix of the paper for a little more detail. Comments and suggestions are more than welcome.
(March 29, 2016) Gave a talk at the UW CS Theory Seminar: Combinatorial polytopes in algebraic and geometric complexity theory, about this paper and a forthcoming paper with Ketan Mulmuley and Youming Qiao.
2015 Updates
(December 20, 2015) Quoted several times in a WIRED front-page article by Erica Klarreich about the recent breakthrough on Graph Isomorphism (reprinted from Quanta).(November 3, 2015) Updated Monotone projection lower bounds from extended formulation lower bounds with new lower bound against reductions from perfect matchings in general graphs to perfect matchings in bipartite graphs.
(October 29, 2015) New paper posted: Network structure at multiple scales via a new network statistic: the onion decomposition, joint with Laurent Hébert-Dufresne and Antoine Allard.
(October 28, 2015) New paper posted: Monotone projection lower bounds from extended formulation lower bounds.
(October 12-16, 2015) Organized the SFI Workshop on Wildness in Computer Science, Physics, and Mathematics.
(October 8, 2015) New paper posted: Graph isomorphism and circuit size, joint with Eric Allender and Cris Moore.
(October 1, 2015) Eric Allender gave a great 15-minute talk at the Simons Institute for the Theory of Computing on our most recent joint work with Cris Moore, "Graph Isomorphism and Circuit Size."
(August 31, 2015) Polynomial-time isomorphism test of groups that are tame extensions accepted to ISAAC 2015 (the leading conference on algorithms in (East) Asia).
(July 14, 2015) You can listen to my interview by @Samuel_Hansen for the Strongly Connected Components podcast. My segment starts at 40:45, but you should also listen to the preceding interviews with my colleagues Yoav Kallus and Sid Redner!
(July 7, 2015) New paper posted: Polynomial-time isomorphism test of groups that are tame extensions (joint w/ Youming Qiao).
(May 9, 2015) The final, significantly expanded and edited version of Unifying known lower bounds via geometric complexity theory has now appeared in Computational Complexity, and is freely available forever (thanks to funding from SFI).
(Apr 21, 2015) Gave a CS colloquium at UNM: The role of symmetry (or the lack thereof) in algorithms and computational complexity.