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, with recent exciting connections to metacomplexity and proof complexity. The workshop brings together experts from these fields.

Each plenary speaker will explain a recent result and break down its main ideas to a level that is accessible for the mathematically diverse audience.

Time and Place

Monday 2025-March-17 to Friday 2025-March-21

Mathematics Lecture Hall B3.02Link opens in a new window, Zeeman Building, Warwick Mathematics Institute, The University of Warwick, Coventry, UK

We will use the lecture hall's equipment to enable remote participation. If you are interested in remote participation please write an email to jakob.moosbauer@warwick.ac.uk then we will send you the link for the remote session, you do not need to register with the form.

Registration

Registration is closed.

Plenary Speakers

• Fulvio GesmundoLink opens in a new window, Paul Sabatier University, Toulouse, France
• Michael WalterLink opens in a new window, Ruhr University Bochum, Germany
• Greta PanovaLink opens in a new window, University of Southern California, USA
• Rahul SanthanamLink opens in a new window, Oxford University

Schedule

All times GMT	Mon 17	Tue 18	Wed 19	Thu 20	Fri 21
	9:00 Registration, 9:15 Opening remarks		Room MSB2.22 9:00-9:15 Dimitrios Tsintsilidas 9:34-9:51 Jinqiao Hu
09:30-10:15	Fulvio Gesmundo (1)	Michael Walter (1)	10:00-10:45 Greta Panova (1)	Jeong-Hoon Ju	Rahul Santhanam (1)
10:15-10:45	coffee break	coffee break	10:45-11:15 coffee break	coffee break	coffee break
10:45-11:30	Fulvio Gesmundo (2)	Michael Walter (2)	11:15-12:00 Greta Panova (2)	Dimitrios Tsintsilidas	Rahul Santhanam (2)
11:45-12:30	open problems (1)	Vladimir Lysikov	12:00-12:45 Dhara Thakkar	Chia-Yu Chang	Hanlin Ren
12:30-14:00	lunch	lunch	lunch	lunch	lunch
14:00-14:45	open problems (2)	Maxim van den Berg	Ramya C	Christian Ikenmeyer
14:45-15:15	coffee break	coffee break	coffee break	coffee break	coffee break
15:15-16:00	Joshua Grochow	Jakob Moosbauer	Harold Nieuwboer	Vishwas Bhargava

On Wednesday, Warwick Computer Science runs its Postgraduate ColloquiumLink opens in a new window in room MSB2.22 with two complexity theory talks. You are welcome to attend. Hence, on Wednesday the workshop sessions start at 10:00.

Abstracts (sorted alphabetically by last name)

• Maxim van den Berg (VideoLink opens in a new window)
  Computing moment polytopes, with applications in algebraic complexity
  Moment polytopes are compact convex polytopes associated to a tensor that contain geometric and asymptotic representation-theoretic information. They are central objects in non-commutative optimization (scaling problems), in Strassens theory of asymptotic spectra to study matrix multiplication (via the quantum functionals), and in quantum information theory. However, only a very small number of explicit examples of these polytopes were previously known. We present a new algorithm based on a description due to Franz, and use it to greatly extend the amount of available examples. The examples serve as inspiration for new theoretical results: among other results, we prove the first separation of the moment polytopes of the (iterated) matrix multiplication tensors and the unit tensors, and we give the first ever explicit construction of a family of tensors that are not free in any basis.
• Vishwas Bhargava (VideoLink opens in a new window)
  Partial Derivatives, Waring Rank, and Commutative ROABPs
  The dimension of the space of partial derivatives is a well-known measure for proving lower bounds in algebraic complexity. But what can we say about polynomials whose partial derivative dimension is polynomially bounded?
  It is conjectured that such polynomials should also have a polynomially bounded Waring rank. We discuss this conjecture and show that a bound on the dimension of partial derivatives indeed implies a bound on the commutative ROABP complexity.
  Our proof leverages apolar ideals and establishes a connection between down-closed derivative spaces and commutative matrix spaces.
  Joint work with Anamay Tengse.
• Ramya C (VideoLink opens in a new window)
  Algebraically Natural Proofs: Barriers and Beyond
  In Algebraic Complexity, we are interested in the complexity of computing multivariate polynomials over a field and arithmetic circuits are a natural computational model for polynomials. The number of arithmetic operations needed to compute a polynomial is captured by the size of the circuit computing it. Valiant (1979) conjectured that there are explicit polynomials (for instance, the permanent polynomial) that are hard to be computed by circuits of size polynomial in the number of variables. Despite consistent efforts, the best-known size lower bounds for general circuits is barely super-linear. However, strong lower bounds are known for several structured classes of circuits and most known lower bounds can be unified under the framework of "algebraically natural proofs" introduced by Grochow, Kumar, Saks, Saraf (2017) and Forbes, Shpilka, Volk (2018). We will review this natural recipe for proving arithmetic circuit size lower bounds. While some believe that this framework cannot be extended to settle the truth of Valiant’s conjecture, some of our recent results highlight the existence of natural lower bound techniques for proving lower bounds against certain rich subclasses of arithmetic circuits.
• Chia-Yu Chang (VideoLink opens in a new window)
  Generic Border Subrank
  The subrank and border subrank play central roles in several areas including algebraic complexity theory, quantum information theory, and combinatorics. In this talk, I will define subrank and border subrank of tensors, which are generalizations of matrix rank and first introduced by Strassen. The rank and border rank of a generic tensor are the same and equal to the maximal border rank. However, we know less about the behavior of the subrank and border subrank. I will state the main result that the growth rate of the generic subrank is the same as the growth rate of the generic border subrank. Then I will give an idea of proof of the main result. This is joint work with Benjamin Biaggi, Jan Draisma, and Filip Rupniewski.
• Fulvio Gesmundo (VideoLink opens in a new window)
  Apolarity theory, zero-dimensional schemes and their role in complexity theory
  We give an introduction to classical apolarity theory, which is central in the study of Waring rank of homogeneous polynomials. We use apolarity to introduce the notion of cactus rank and discuss some consequences in complexity theory. In particular, we give a geometric explanation of the barrier for rank methods for lower bounds on (border) Waring rank, and we illustrate a recent debordering result obtained by using normal forms arising from "cactus decompositions".
• Joshua Grochow (VideoLink opens in a new window)
  Gröbner bases in algebras with straightening law
  Off-the-shelf Gröbner basis methods are too inefficient to handle even some of the smallest cases of orbit closures that arise in geometric complexity theory, such as the orbit closure of the 3x3 determinant. Motivated by this difficulty, we attempt to take advantage of the determinantal and representation-theoretic structure of these varieties by developing a theory of Gröbner bases in algebras with straightening law (ASLs, also sometimes called Hodge algebras). We instantiate our Gröbner basis theory in the bideterminant ASL structure on a a polynomial ring - given by the products of minors of a variable matrix - where we call our objects bd-Gröbner bases. Our theory packages a number of results about bideterminants in a clean way, enabling us to give a one-line proof of a bd-Gröbner basis for the maximal minors of a matrix, whose ordinary Gröbner bases are well-known but whose proofs are more involved.
  Joint work with Abhiram Natarajan (who will soon be on the job market!).
• Christian Ikenmeyer (VideoLink opens in a new window)
  Algebraic metacomplexity and representation theory
  In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. We use this to resolve an open question posed by Grochow, Kumar, Saks and Saraf (2017). Our result means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, it means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincaré-Birkhoff-Witt theorem for Lie algebras and on Gelfand-Tsetlin theory.
• Jeong-Hoon Ju (VideoLink opens in a new window)
  Recursive Koszul Flattenings of Determinant and Permanent Tensors
  In complexity theory, there have been several attempts to compare determinant and permanent, for example, with respect to determinantal complexity, border determinantal complexity and Ulrich complexity. On the other hand, both determinant and permanent are multilinear maps, i.e., are tensors and tensor rank measures complexity of tensors in one sense. In this talk, we compare determinant and permanent tensors in terms of tensor rank. At first, we review the notion of tensor rank and some known tensor rank bounds of determinant and permanent tensors. Then we focus on lower bound and introduce a linear-algebraic framework to improve the lower bound, which is called rank method. As an example of the rank method, we look into the method which Hauenstein-Oeding-Ottaviani-Sommese suggested. We call it recursive Koszul flattening. Using this and representation theory, we improve tensor rank lower bounds of the determinant and permanent tensors. This approach not only gives the exact tensor rank of 4 x 4 determinant and permanent tensors but also separates determinant and permanent tensors in terms of tensor rank. Lastly, we discuss future works. This is joint work with Jong In Han and Yeongrak Kim.
• Vladimir Lysikov (VideoLink opens in a new window)
  Complexity theory of orbit closure intersection
  Many natural computational problems amount to deciding if two objects are equivalent. Often this equivalence is defined in terms of group actions. A natural question is to ask when two objects can be distinguished by polynomial functions that are invariant under the group action. For finite groups, this is the usual notion of equivalence, but for continuous groups like the general linear groups it gives rise to a new notion, called orbit closure intersection. It captures, among others, the graph isomorphism problem, noncommutative PIT, null cone problems in invariant theory, equivalence problems for tensor networks, and the classification of multiparty quantum states. Despite recent algorithmic progress in celebrated special cases, the computational complexity of general orbit closure intersection problems is currently unclear. In particular, tensors seem to give rise to the most difficult problems.
  We study orbit closure intersection problems for tensors and tensor tuples from the complexity-theoretic viewpoint and define an appropriate notion of algebraic reductions that imply polynomial-time reductions in the usual sense, but are amenable to invariant-theoretic techniques. We identify natural tensor problems that are complete for the class of orbit closure intersection problems (one such complete problem is the equivalence of 2D tensor networks with constant physical dimension) and show that the graph isomorphism problem can be reduced to these complete problems, which implies that many orbit closure intersection problems are GI-hard.
• Jakob Moosbauer (VideoLink opens in a new window)
  The Orbit Rank of Tensors and Complexity of Matrix Multiplication
  In this talk I introduce the concept of G-orbit rank of a tensor for finite groups G. The orbit rank is the minimal number of group orbits needed in a decomposition of a tensor T under the action of a symmetry group. We will show how the orbit rank relates to the complexity of matrix multiplication and present some upper bounds on the orbit rank of the matrix multiplication tensor for different groups. We then use them to derive bounds on the tensor rank.
• Harold Nieuwboer (VideoLink opens in a new window)
  Asymptotic tensor rank is characterized by polynomials
  Asymptotic tensor rank is notoriously difficult to determine. Indeed, determining its value for the 2x2 matrix multiplication tensor would determine the matrix multiplication exponent, a long-standing open problem. On the other hand, Strassen's asymptotic rank conjecture makes the bold claim that asymptotic tensor rank equals the largest dimension of the tensor and is thus as easy to compute as matrix rank. Despite tremendous interest, much is still unknown about the structural and computational properties of asymptotic rank; for instance whether it is computable. We prove that asymptotic tensor rank is "computable from above", that is, for any real number r there is an (efficient) algorithm that determines, given a tensor T, if the asymptotic tensor rank of T is at most r. The algorithm has a simple structure; it consists of evaluating a finite list of polynomials on the tensor. Indeed, we prove that the sublevel sets of asymptotic rank are Zariski-closed (just like matrix rank). While we do not exhibit these polynomials explicitly, their mere existence has strong implications on the structure of asymptotic rank. As one such implication, we find that the values that asymptotic tensor rank takes, on all tensors, is a well-ordered set. In other words, any non-increasing sequence of asymptotic ranks stabilizes ("discreteness from above"). In particular, for the matrix multiplication exponent (which is an asymptotic rank) there is no sequence of exponents of bilinear maps that approximates it arbitrarily closely from above without being eventually constant. In other words, any upper bound on the matrix multiplication exponent that is close enough, will "snap" to it. Previously such discreteness results were only known for finite fields or for other tensor parameters (e.g., asymptotic slice rank). We obtain them for infinite fields like the complex numbers.
• Greta Panova (VideoLink opens in a new window)
  The Kronecker coefficients: standard and reduced
  The Kronecker coefficients of the Symmetric group give the multiplicity of an irreducible representation in the tensor product of another two irreducibles. They pose a major mystery in Algebraic Combinatorics and Representation Theory as no nice combinatorial interpretation for them has been found almost 90 years since their introduction. They also play crucial roles in Geometric Complexity Theory. The reduced Kronecker coefficients, called "extended Littlewood-Richardson" by Kirilov, were defined as their stable limits and considered easier.
  In this talk we will cover the basic definitions and see how to compute and understand the Kronecker coefficients. We will then show that all Kronecker coefficients are in fact reduced Kronecker coefficients establishing that the two open problems on finding each of their combinatorial interpretations [Stanley'00,Kirilov/Klyachko'04] are, in fact, equivalent.
• Rahul Santhanam (VideoLink opens in a new window)
  No Short AC⁰[p]-Frege Proofs for Conjectured Tautologies
• Hanlin Ren (VideoLink opens in a new window)
  Polynomial-Time Pseudodeterministic Construction of Primes
• Dhara Thakkar (VideoLink opens in a new window)
  On the Efficient Computation of Certain Invariants of Groups
  Cayley's theorem says that every finite group G can be viewed as a subgroup of symmetric group S_m for some integer m. The minimal faithful permutation degree, μ(G) of a finite group G is the smallest integer m such that G is isomorphic to a subgroup of S_m. In this talk, we will see an efficient algorithm for computing the minimal faithful permutation degree of groups without abelian normal subgroups.
  This talk is based on the joint work with Bireswar Das, Michael Levet, and Pranjal Srivastava.
• Dimitrios Tsintsilidas (VideoLink opens in a new window)
  Field-independent Kronecker-plethysm isomorphisms
• Michael Walter (VideoLink opens in a new window)
  Computational complexity of orbit problems

Organisers: Christian IkenmeyerLink opens in a new window and Jakob MoosbauerLink opens in a new window

Related Workshops

The 8th Workshop on Algebraic Complexity Theory (WACT)Link opens in a new window will be held two weeks later in Bochum, Germany, and one of our plenary speakers, Michael Walter, is an organiser. The 7th WACTLink opens in a new window was at Warwick in 2023.