Complexity in Michigan

Invited Speaker Nutan Limaye, Conference Chair Valentine Kabanets,
2024 PC Chair Rahul Santhanam, myself, 2025 PC Chair Srikanth Srinivasan
and 2025 Local Arrangements chair Swastik Kopparty enjoy some tapas.

I have a long history with the Computational Complexity conference. I attended the first 26 meetings (1996-2011) and 30 of the first 31. I chaired the conference committee from 2000-2006. According to DBLP I still have the most papers appearing in the conference (32). I even donated the domain name for the conference (with the caveat that I could keep the subdomain for this blog).

Only Eric Allender had a longer streak having attended the first 37 conferences through 2022 in Philadelphia (if you count the two online during the pandemic) before he retired.

But I haven't been back to Complexity since that 31st conference in Tokyo in 2016. Due to my administrative roles, various conflicts and changes in the field you just start missing conferences. But with the conference at the University of Michigan in Ann Arbor within driving distance of Chicago it was time to go home for the 39th meeting. And it's a good thing I drove as more than one person had flight delays due to the Crowdstrike bug.

The complexity conference remains relatively stable at about 75-100 registrants, the majority students and young researchers. I've moved from wise-old sage to who is that guy. But I'm having great fun talking to old acquaintances and new. I'm impressed with the newer generations of complexity theorists--the field is in good hands.

Best paper goes to Michael Forbes Low-Depth Algebraic Circuit Lower Bounds over Any Field. the work of Limaye, Srinivasan and Tavenas I talked about last month gave an explicit polynomials with superpolynomial-size over constant depth algebraic circuits but it required polynomials over large fields. Forbes extended the lower bounds to all field sizes.

Best student paper goes to Ted Pyne from MIT for Derandomizing Logspace with a Small Shared Hard Drive for showing how to reduce space for randomized log-space algorithms on catalytic machines.

Check out all the papers in the online proceedings.

From a relatively quiet business meeting: 36 papers accepted out of 104 submissions, a bit up from previous years. 75 attendees including 42 students, similar to recent years. 2025 conference at the Fields Institute in Toronto August 5-8. 2026 in Lisbon or Auckland.

The loss of Luca Trevisan, PC Chair 2005 and local arrangements chair in 2013 in San Jose, loomed large in the business meeting and at the conference.