8th Workshop on Algebraic Complexity Theory (WACT 2025)

Organizers: Maxim van den Berg (RUB/UvA), Vladimir Lysikov (RUB), Michael Walter (RUB), Jeroen Zuiddam (UvA), Janine Hein (RUB)
Date & Time: March 31-April 4, 2025
Venue: Ruhr University Bochum, Lecture Hall HGD 20
Registration: Registration is closed. Please contact Janine Hein about last-minute registration.

Scientific Program

Algebraic Complexity Theory is a vibrant field that has been seeing a tremendous amount of activity in the recent years. Its classical questions have been interwoven with deep questions from algebraic geometry, invariant theory, and representation theory. Researchers study a wide range of interlinked topics: arithmetic circuit lower bounds, algorithmic algebra, algorithmic invariant theory, geometric complexity theory, tensor rank, polynomial identity testing, polynomial reconstruction, quantum information, and quantum complexity theory, to name a few. The workshop brings together experts from different parts of this rich field to discuss the current state of the art, discover new connections, and set the directions for the future. This year we are particularly hoping to attract researchers across all disciplines that are broadly interested in making new connections between algebra and computation.

Tentative Schedule

Time Monday Tuesday Wednesday Thursday Friday
9:00-9:30 Registration
9:30-10:20 Christian Ikenmeyer
Algebraic and geometric complexity theory		 Markus Bläser
(Un)expected appearance of algebraic complexity in machine learning		 Pranjal Dutta
A brief survey on de-bordering paradigms and its recent advances		 Petteri Kaski
Sequences of three-tensors and algorithms for hard problems		 Youming Qiao
Tensor Isomorphism: complexity, algorithms, and cryptography
10:20-10:40 Coffee break
10:40-11:30 Nitin Saxena
Closure of algebraic complexity classes under factoring		 Weronika Buczyńska
Introduction to border apolarity		 Jan Draisma
Uniformity for limits of tensors		 Robert Andrews
Constant-Depth Arithmetic Circuits for Linear Algebra Problems		 Michael Forbes
11:30-11:40 Short break
11:40-12:05 Amir Shpilka
The sparsity challenge: many questions, few answers		 Milind Sohoni
Stabilizer Limits and Orbit Closures in Geometric Complexity Theory		 Harold Nieuwboer
Asymptotic tensor rank is characterized by polynomials		 Chris Umans
Matrix multiplication algorithms from infinite groups		 Partha Mukhopadhyay
Trading Determinism for Noncommutativity in Singularity Testing
12:05-12:30 Amichai Lampert
Equivalence of some notions of rank for 3-tensors		 Chia-Yu Chang
Generic Border Subrank
12:30-14:00 Lunch break
14:00-14:50 Ankit Garg
Arithmetic circuits: learning, lower bounds and applications		 Greta Panova
Complexity and asymptotics of representation theoretic multiplicities		 Michèle Vergne
Quivers, multiplicities, and polytopes		 Olga Holtz
Fast Matrix Multiplication: Theory and Practice		 Open problems
session
14:50-15:10 Coffee break
Excursion
(15:00-18:00)
 
Dinner
(at 18:00)
 Coffee break
15:10-16:00 Srikanth Srinivasan
How do we prove lower bounds on algebraic formulas?		 Kathlén Kohn
Algebraic Complexity of Computer Vision Problems		 Time for
collaboration		 Time for
collaboration
16:00-18:00 Poster session
and reception		 Time for
collaboration

Travel and Venue

  • Air and train travel: Bochum can be reached by train from major airports including Düsseldorf, Dortmund, Frankfurt, Cologne/Bonn. Because of surprise rail renovations, long distance trains currently do not stop at Bochum train station, and on weekends the local S1 trains may also be unavailable. To reach Bochum, one can take regional trains RE1 or RE3 from Essen or Duisburg to Herne train station, and use the underground line U35 line from Herne to reach central Bochum (and also the university). We recommend planning your journey using the Deutsche Bahn web page.
  • From Bochum main train station (city center): Follow the “U” signs and take underground line U35 (CampusLinie) in direction Bochum Hustadt, until you arrive at stop Ruhr-Universität. On workdays, the U35 departs every five minutes; it takes about 10 minutes to reach the university.
  • Once you arrive on campus: Please see the campus map below. Once you arrive at building GD, take the stairs or elevator down one level to arrive at lecture hall HGD 20.

See also Google Maps (but don’t trust its pedestrian navigation on campus!).

Registration and Early-Career Support

To attend the workshop, please register by filling out the Registration Form. Participation in the workshop is free of charge.

  • Early-Career Support: We have limited budget to support early career researchers participating in WACT. To apply, please (1) send an email to Janine Hein with the subject line “WACT 2025 Early Career”, including your CV and a short motivation letter, and (2) arrange for a recommendation letter from an academic supervisor to be sent to the same address with the subject line “WACT 2025 Early Career Recommendation” (this letter should also indicate any other funding available). Please submit all materials by February 9. We hope to notify applicants by February 14.

  • Invitation Letter: If you need an invitation letter or a similar document (e.g., to support your visa application), please send an email to Janine Hein with the title “WACT 2025 Invitation letter” and include all required information.

Previous WACTs

Accommodation

It has come to our attention that some attendees received emails from “Global Travel Team” about hotel booking. These emails are scam: all communication regarding the workshop organization and the support for invited speakers and early career researchers will come directly from the organizers.

We will arrange accommodation for the invited speakers. Participants are free to book any accommodation of their choice. Here are some options for reference, but there are many others and we recommend that you do your own research before making a decision: