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

Workshop Photo

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 aims to bring together researchers across disciplines that are broadly interested in making connections between algebra and computation – to discuss the current state of the art, discover new connections, and set the directions for the future.

Scientific Program

Please feel warmly invited to also attend the Quantum Information Workshop that will be organized on Monday Apr 7, right after WACT.

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
Low-Depth Algebraic Circuit Lower Bounds over Any Field 📥 🎬
11:30-11:40 Short break
11:40-12:05 Amir Shpilka
Challenges In and Around Sparse Polynomial Factorization 📥 🎬		 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
Computational complexity of representation theoretic quantities 📥 🎬 		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
(Room 143 available
16:00—18:00)		 Time for
collaboration
(Room 143 available
16:00—18:00)
16:00-18:00 Poster session
and reception		 Time for
collaboration
(Room 153 available)

Venue

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.

Also useful:

Travel

  • Air and train travel: Bochum can be reached by train from major airports including Düsseldorf, Dortmund, Frankfurt, Cologne/Bonn. 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 above.

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

Previous WACTs