WACT Abstracts

Click here to return to the workshop homepage.

Monday

• Christian Ikenmeyer (University of Warwick): Algebraic and geometric complexity theory

  In this talk, I will give an introduction to some concepts that appear in geometric complexity theory, and I will present some recent results and survey a list of open problems.

• Nitin Saxena (IIT Kanpur): Closure of algebraic complexity classes under factoring

  Polynomial factoring is one of the most fundamental problems in the area of computational algebra. Its variants have attracted a huge amount of attention in the last half-a-century. On the other hand, algebraic complexity theory classifies polynomials, into complexity classes, according to computational resources. Could we show that these classes afford polynomial factoring algorithms?

  In this talk we will focus on four algebraic complexity classes — size s circuits VP_nb, size s degree s circuits VP, size s degree s verifier circuits VNP, and size s algebraic branching programs VBP. We will discuss the algebraic methods, inspired from analysis, that have been developed to do factoring in these complexity classes. We will list the open questions and make some related conjectures.

  (This is based on the joint work with Pranjal Dutta, Amit Sinhababu (J.ACM’22, STOC’18), and the follow-up papers by others.)

• Amir Shpilka (Tel Aviv University): The sparsity challenge: many questions, few answers

• Ankit Garg (Microsoft Research India): Arithmetic circuits: learning, lower bounds and applications

  Arithmetic circuits are a natural model for computing polynomials via the basic operations of addition and multiplication. The problem of learning arithmetic circuits is the following: given a polynomial (using black box access), output a small arithmetic circuit computing it (if one exists). This problem is NP-hard in very simple settings. I will present a meta framework for learning arithmetic circuits in the generic case using lower bound methods. We instantiate and implement this meta framework for various classes of arithmetic circuits. Then I will talk about extending the algorithms to the noisy setting and applications to classical problems in machine learning like subspace clustering and mixtures of Gaussians.

  This is based on joint works with Pritam Chandra, Neeraj Kayal, Kunal Mittal, Chandan Saha and Tanmay Sinha.

• Srikanth Srinivasan (University of Copenhagen): How do we prove lower bounds on algebraic formulas?

  Proving lower bounds on the size of algebraic formulas computing an explicit polynomial is a longstanding open problem in complexity theory. In this survey talk, I will give a biased account of some old and recent attempts aimed towards resolving this question.

Tuesday

• Markus Bläser (Saarland University): (Un)expected appearance of algebraic complexity in machine learning

  We present how two concepts from algebraic complexity theory appear in machine learning.

• Weronika Buczyńska (University of Warsaw): Introduction to border apolarity

  The border rank of F is the minimal r such that F is a limit of polynomials of rank at most r. The motivating and still unsolved problem that lead to the border apolarity method introduced in my joint work with Jarek Buczyński was to find the border rank of monomials. Their rank was know only since 2011. These simplest of polynomials admit a lot of symmetries — as they are preserved by the torus action. The dream was to get the apolarity method work in the way that it will be possible to perform finite computations for border rank.

  To compute the border rank of F we consider flat families of pointsso that the limiting linear span contains F. The key observation is that one can assume that the Hilbert function in that family is constant. Moreover, that it is enough to consider the Hilbert function of r generic points. This means that the multigraded Hilbert scheme is the key object to understand border rank. Additionally, when F in question is invariant under action of a solvable connected algebraic group, to obtain estimates of border rank only the invariant points of the multigraded Hilbert scheme are relevant. In the monomial case the question is reduced to the existence of monomial subideals of the apolar ideal of F.

  The border decomposition of length r of a polynomial (tensor, partially symmetric tensor) is an ideal that is a limit of ideals of r points. One of the obstacles for the computations are ideals that have this particular Hilbert function, but they do not provide a border decomposition as they are not in the SLIP (Set of Limits of Ideals of Points) subset of the multigraded Hilbert scheme.

  The work of Tomasz Mańdziuk in his PhD thesis followed by his joint work with Joachim Jelisiejew provides some ways to overcome this barrier.

• Milind Sohoni (IIT Bombay): Stabilizer Limits and Orbit Closures in Geometric Complexity Theory

  By Valiant’s result, the determinant is a master function in computational complexity theory — any form f(X) appears as the evaluation of a suitably large determinant det_n(AX)$, with entries as affine linear combinations AX of X. A may be called the implementation of f(X) as a determinant. A classical question has been — How big a determinant det_n is required to compute a suitably padded permanent perm’_m?

  The Geometric Complexity approach casts this as an orbit closure problem in the space of forms Symⁿ(X). We have the padded permanent as the point z=perm’_m (with stabilizer H’_m) lying in the projective orbit closure of the special form det_n(X) as the point y (with stabilizer K_n) via the 1-parameter subgroup λ arising out of the implementation A. The problem is to arrive at “obstructions” based on the stabilizers K_n and H’_m. This has been approached by many researchers using representation theory with several negative and positive results.

  We develop a Lie algebraic approach to the problem which allows a more geometric analysis. Here 𝔨 and 𝔥, the Lie algebras of K_n and H’_m are the central objects. Using λ-weights and leading terms, we develop a theory of how stabilizers change under taking limits. We show that the leading terms 𝔨̂ of the Lie algebra 𝔨 form a special Lie sub-algebra of 𝔥. This is the first known connection between the two stabilizers. We next define alignment, i.e., semisimple elements s∈H∩K and show how their presence leads to combinatorial conditions on the implementation A. We also show how attributes of 𝔨̂→𝔥 lead us to structures which further connect 𝔥 and 𝔨 and point to orbits intermediate to O(y) and O(z).

  The central question in this approach is on the nature of alignments, conditions for the same, and their absence. We show that this connects with many classical analyses of orbit closures, viz., of Hilbert-Mumford-Kempf, toric varieties and compactifications of Lie groups. This leads to many interesting combinatorial structures associated with the determinant. These are also presented.

  The overall agenda is to exhibit the determinant as a master group — in other words, a recipe to construct a desired stabilizer group family H’_m as a sequence of orbits and their stabilizers.

  This is joint work with K.V.Subrahmanyam and Bharat Adsul.

• Greta Panova (University of Southern California): Computational complexity of representation theoretic quantities

  Representation Theoretic multiplicities and characters of representations are central quantities in Algebraic Combinatorics, Representation Theory and are heavily involved in Geometric Complexity Theory. Understanding the behavior of such quantities is crucial for the search of multiplicity obstructions in GCT for establishing computational lower bounds. In this talk we will briefly recap the connection to GCT and then discuss recent results on the classical and quantum computation of Kronecker and plethysm coefficients. We will also show that the characters of the symmetric group are as hard as PH (joint with Ikenmeyer, Pak).

• Kathlén Kohn (KTH Stockholm): Algebraic Complexity of Computer Vision Problems

  The state-of-the-art pipelines for 3D reconstruction from 2D pictures use a mix of machine learning, optimization tricks, and fast polynomial system solving. The polynomial systems appearing in these pipelines have to be solved thousands of times, which is why it is tremendously important to work with polynomial systems of low algebraic complexity. In this talk, I present strategies on how to systematically find such low-complexity systems. The polynomial systems appearing in 3D-reconstruction come in 2 flavors: They either model computing a fiber under a finite algebraic map (in which case the algebraic complexity is given by the degree of the map) or Euclidean-distance minimization on an algebraic variety (where the number of complex critical points measures the algebraic complexity). Thus, the strategies we explore include navigating huge families of finite algebraic maps and re-weighting optimization problems to obtain a minimal number of critical points.

Wednesday

• Pranjal Dutta (National University of Singapore): A brief survey on De-bordering paradigms and its recent advances

  Border complexity of polynomials plays a crucial role in the Geometric Complexity Theory (GCT) approach to separating P from NP. Defined via limits or topological closures, border complexity captures functions that can be approximated arbitrarily closely by low-complexity functions. Debordering refers to the task of proving upper bounds on non-border complexity measures in terms of border complexity measures, effectively eliminating the need for limits. A classical example of debordering is Bini’s result on matrix multiplication tensors, which was instrumental in the development of fast matrix multiplication algorithms. However, despite its significance, only a handful of debordering results are currently known. In this talk, I will survey recent progress in debordering for many restrictive complexity measures, and their implications for algebraic complexity theory.

• Jan Draisma (University of Bern): Uniformity for limits of tensors

  By classical algebraic geometry, if f is a polynomial map that takes as input some vectors in a vector space V, matrices in V⊗V, and higher-order tensors, and that outputs an element in a tensor power of V, then any tensor in the image closure of f is a limit for ε→0 of f(T(ε)), where T(ε) depends as a Laurent polynomial on ε. I will discuss a strengthening of this result that says that if f is functorial in V, then the negative powers of ε in T(ε) can be bounded from below independently of the dimension of V. A consequence is a debordering result for a rather general class of tensor ranks, albeit of a qualitative rather than quantitative nature. This result is derived from a curve selection lemma in infinite-dimensional algebraic varieties with an action of the infinite general linear group, and I will present some of the main ideas in this theory.

  (Joint work with Arthur Bik, Rob Eggermont, and Andrew Snowden.)

• Harold Nieuwboer (University of Copenhagen): Asymptotic tensor rank is characterized by polynomials

  Asymptotic tensor rank is notoriously difficult to determine. Indeed, determining its value for the 2×2 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.

  Based on joint work with Matthias Christandl, Koen Hoeberechts, Péter Vrana and Jeroen Zuiddam.

• Amichai Lampert (University of Michigan): Equivalence of some notions of rank for 3-tensors

  There are various ways to quantify how non-degenerate a 3-tensor is. Among these are slice rank, analytic rank and geometric rank. These three notions have found numerous applications in various fields across math and computer science. There are some fairly straightforward inequalities between these ranks and it was conjectured that in fact they are all equivalent, in the sense of being bounded by linear functions of each other. This was proved thanks to the work of Derksen, using geometric invariant theory. I will discuss a recent (mostly) elementary proof of this result.

  Partly joint with Benjamin Baily.

• Michèle Vergne (Paris): Quivers, multiplicities, and polytopes

  Let G be a compact Lie group acting on a vector space H. The space of polynomials on H decomposes as a sum with multiplicities m_H(λ) of irreducible representations of G. The set of points λ where m_H(λ) is non zero is (almost) the set of integral points in a polyhedral cone. Furthermore, it is sometimes possible to describe m_H(λ) as the number of integral points in a polytope. For example, the set of triples (λ, μ, ν) where the Clebsch-Gordan coefficient c^ν_λ,μ is non zero is described by the Horn inequalities, while the number c^ν_λ,μ is the number of integral points in the Knutson-Tao polytope. When H = H_d is the representation space of a quiver associated to a dimension vector d, one can give similar descriptions of m_Hd(λ).

  This is joint work with Michael Walter.

Thursday

• Petteri Kaski (Aalto University): Sequences of three-tensors and algorithms for hard problems

• Robert Andrews (University of Waterloo): Constant-Depth Arithmetic Circuits for Linear Algebra Problems

  How does one compute the greatest common divisor (GCD) of two univariate polynomials? The Euclidean algorithm computes the GCD in polynomial time, and fast variants of the Euclidean algorithm can solve this problem in nearly-linear time. The GCD can also be expressed in a linear-algebraic form. Basic tasks in linear algebra such as computing determinants and solving linear systems can be performed in O(log² n) parallel time, and this can be used to compute the GCD in O(log² n) parallel time. This algorithm does not take advantage of any structure present in the resulting linear systems, so in principle one could compute the GCD in parallel even faster.

  In this talk, I will describe a new algorithm that computes the GCD in O(log n) parallel time by using a combination of polynomial interpolation and Newton’s identities for symmetric polynomials. In fact, this algorithm can essentially be implemented as an arithmetic circuit of constant depth. Similar ideas yield constant-depth circuits to compute the resultant, Bézout coefficients, and squarefree decomposition.

  Based on joint work with Avi Wigderson.

• Chris Umans (Caltech): Matrix multiplication algorithms from infinite groups

  The Cohn–Umans (FOCS ’03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group G satisfying a simple combinatorial condition (the Triple Product Property). The complexity of such an algorithm then depends on the representation theory of G. We extend the group-theoretic framework to the setting of infinite groups. In particular, this allows us to obtain constructions in Lie groups, with favorable parameters, that are provably impossible in finite groups of Lie type (Blasiak, Cohn, Grochow, Pratt, and Umans, ITCS ’23). Previously the Lie group setting was investigated purely as an analogue of the finite group case; a key contribution in this paper is a fully developed framework for obtaining bona fide matrix multiplication algorithms directly from Lie group constructions.

  As part of this framework, we introduce “separating functions” as a necessary new design component, and show that when the underlying group is G = GL_n, these functions are polynomials with their degree being the key parameter. In particular, we show that a construction with “half-dimensional” subgroups and optimal degree would imply ω = 2. We then build up machinery that reduces the problem of constructing optimal-degree separating polynomials to the problem of constructing a single polynomial (and a corresponding set of group elements) in a ring of invariant polynomials determined by two out of the three subgroups that satisfy the Triple Product Property. This machinery combines border rank with the Lie algebras associated with the Lie subgroups in a critical way.

  We give several constructions illustrating the main components of the new framework, culminating in a construction in a special unitary group that achieves separating polynomials of optimal degree, meeting one of the key challenges. The subgroups in this construction have dimension approaching half the ambient dimension, but (just barely) too slowly. We argue that features of the classical Lie groups make it unlikely that constructions in these groups could produce nontrivial bounds on ω unless they prove ω = 2. One way to get ω = 2 via our new framework would be to lift our existing construction from the special unitary group to GL_n, and improve the dimension of the subgroups from (dim G)/2 − Θ(n) to (dim G)/2 − o(n).

• Olga Holtz (UC Berkeley & TU Berlin): Fast Matrix Multiplication: Theory and Practice

  This talk examines the gap between theoretical advances in matrix multiplication algorithms and their practical implementations. Beginning with Strassen’s O(n^2.807) algorithm, we survey developments in arithmetic complexity theory, addressing how asymptotic improvements often fail to yield proportional real-world gains. We analyze the critical role of communication complexity (I/O complexity) in modern hierarchical memory architectures and examine recent algorithmic innovations including Karstadt-Schwartz methods, flip graph approaches, and deep learning techniques. The presentation concludes with promising research directions for further reducing the practical complexity of this fundamental operation.

Friday

• Youming Qiao (UT Sydney & IAS): Tensor Isomorphism: complexity, algorithms, and cryptography

  Two matrices are called equivalent if one can be transformed into the other by multiplying with invertible matrices on the left and right. Extending this idea to 3-tensors, it is natural to define two 3-tensors as isomorphic if they can be transformed into each other by multiplication with three invertible matrices along the three directions.

  We show that the problem of testing isomorphism of 3-tensors captures the complexity of testing isomorphism for several algebraic structures, including polynomials, certain families of groups, and associative or Lie algebras. This prompts the introduction of a complexity class called Tensor Isomorphism. Starting from there, we will examine some recent results around Tensor Isomorphism from the perspectives of complexity, algorithms, and cryptography.

• Michael Forbes (University of Illinois): TBD

• Partha Mukhopadhyay (Chennai Mathematical Institute): Trading Determinism for Noncommutativity in Singularity Testing

  Finding an efficient deterministic algorithm for symbolic determinant identity testing (SDIT) is one of the most important problems in computational complexity and very little is known about it. Around 2016, two independent research groups solved the noncommutative version of the problem in deterministic polynomial time (Garg-Gurvits-Oliveira-Wigderson 2016, Ivanyos-Qiao-Subrahmanyam 2017) using very different techniques. In this talk, we will highlight a different algorithm for this problem based on noncommutative polynomial identity testing. Then, I will sketch how this new technique is lifted to solve the singularity problem in the partially commutative setting of variables, which also answers an old question in algebraic automata theory.

  The talk is based on joint work with V. Arvind, and Abhranil Chatterjee.

• Chia-Yu Chang (University of Toulouse): Generic Border Subrank

  The subrank and border subrank play central roles in several areas including algebraic complexity theory. 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 the proof via a generalized version of Hilbert-Mumford criterion.

  This is joint work with Benjamin Biaggi, Jan Draisma, and Filip Rupniewski.