7th Workshop on Algebraic Complexity Theory (WACT) 2023
Time and Place
This is an onsite event. In the unlikely event that public health measures related to COVID19 make physical events infeasible, it will be held in a virtual online format.
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, and polynomial reconstruction, 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.
Plenary Speakers
 Radu Curticapean (IT University of Copenhagen, Basic Algorithms Research Copenhagen)
We are very sad to announce that Heribert Vollmer cannot participate due to health reasons. We wish him all the very best, and a fast and full recovery.
Schedule
Registration
Registration is closed.
Registered Participants
Robert Andrews (University of Illinois UrbanaChampaign),
Amik Raj Behera (Aarhus University),
CS Bhargav (IIT Kanpur),
Vishwas Bhargava (University of Waterloo),
Somnath Bhattacharjee (Chennai Mathematical Institute),
Tejas Bhojraj (Chennai Mathematical Insitute),
Peter Bürgisser (TU Berlin),
Bruno Cavalar (Warwick),
Abhranil Chatterjee (National Institute of Science Education and Research, Bhubaneswar, India),
Prerona Chatterjee (Tel Aviv University),
Suryajith Chillara (International Institute of Information Technology, Hyderabad),
Artur Czumaj (University of Warwick),
Nathaniel Aaron Collins (University of Colorado Boulder),
Manik Dhar (Princeton University),
Prateek Dwivedi (CSE, IIT Kanpur),
Sarah Eggleston (Universität Osnabrück),
Michael Forbes (University of Illinois at UrbanaChampaign),
Hervé Fournier (Université Paris Cité),
Fulvio Gesmundo (Saarland University),
Utsab Ghosal (Chennai Mathematical Institute),
Siddharth Gupta (University of Warwick),
Tom Gur (Warwick),
Christian Ikenmeyer (Warwick),
Neeraj Kayal (Microsoft Research, Bangalore),
Pascal Koiran (ENS Lyon),
Mrinal Kumar (Tata Institute of Fundamental Research),
Deepanshu Kush (University of Toronto),
Martin Lotz (University of Warwick),
Benjamin Lovitz (Northeastern University),
Vladimir Lysikov (University of Copenhagen),
Visu Makam (Radix Trading Europe B. V.),
Guillaume Malod (Université Paris Cité),
Gopinath Mishra (University of Warwick),
Kunal Mittal (Princeton University),
Chandra Kanta Mohapatra (IIT Bombay, India),
Jakob Moosbauer (Johannes Kepler Universität Linz),
Anish Mukherjee (University of Warwick),
Saswata Mukherjee (Chennai Mathematical Institute),
Saraswati Girish Nanoti (IIT Gandhinagar),
Abhiram Natarajan (University of Warwick),
Seyed Sajjad Nezhadi (University of Maryland),
Fedor Part (Institute of Mathematics CAS),
Oleg Pikhurko (University of Warwick),
Aditya Prakash (University of Warwick),
Thejaswini Raghavan (University of Warwick),
Roshan Raj (IIT Bombay),
Ninad Rajgopal (University of Warwick),
Varun Ramanathan (TIFR Mumbai),
Subhayan Saha (ENS Lyon),
Katerina Santicola (University of Warwick),
Nitin Saurabh (Indian Institute of Technology Hyderabad),
Amit Kumar Sinhababu (Chennai Mathematical Institute),
Devansh Shringi (University of Toronto),
Ramanujan Sridharan (University of Warwick),
KV Subrahmanyam (Chennai Mathematical Institute),
Anamay Tengse (University of Haifa),
Dhara Thakkar (IIT Gandhinagar),
Chris Umans (Caltech),
S. Venkitesh (University of Haifa),
Harry Zisopoulos (Saarland University),
Jeroen Zuiddam (University of Amsterdam)
Accommodation
If you travel on your own funds, we recommend the oncampus accommodation Scarman or Radcliffe, but there are many options in Coventry, Kenilworth, and Leamington Spa.
Several bus lines connect the campus with the surrounding area, see the map and the timetables.
Travel
The nearest airport is Birmingham International (BHX), but you can also take the train from London. A train goes from BHX to Coventry; another train goes from London Euston to Coventry. See thetrainline.com. From Coventry several bus lines go to campus regularly, for example 11 or 12X, see the map and the timetables. If your hotel is in Kenilworth, you can take a bus from campus to Kenilworth.
You can take long distance buses instead of trains, in order to avoid the rail strikes on April 1st.
It is a 10 minute walk from the University Interchange bus station to the
Department of Computer Science, which is not necessarily the closest bus station, but the easiest.
Abstracts (sorted alphabetically by last name)

Robert Andrews [slides] [video]
Polynomial Identity Testing via LowRank Matrices
Designing efficient deterministic algorithms for polynomial identity testing (PIT) is a central goal of algebraic complexity theory. For weak circuit classes, such as depththree diagonal circuits and readonce algebraic branching programs, many unconditional results are known. For stronger circuit classes, the hardness versus randomness paradigm allows us to derandomize PIT under various hardness assumptions. Often, these algorithms center around the explicit construction of a hitting set, a pseudorandom object that can be used to certify whether a polynomial is zero or nonzero.
In this talk, I will examine the power of lowrank matrices as a hitting set. Because matrix rank is characterized by the nonvanishing of minors, it is natural to conjecture that lowrank matrices are a hitting set for circuit classes that cannot efficiently compute the determinant. By carefully analyzing the polynomials that vanish on lowrank matrices, we prove this conjecture for lowdepth circuits and for formulas (conditioned on formula lower bounds for the determinant). This yields new hitting set generators with a nearoptimal tradeoff between their seed length and degree and whose output can be computed in quasilinear time.
This talk is based on joint work with Michael A. Forbes.

C. S. Bhargav [slides] [video]
Improved lower bound, and proof barrier, for constant depth algebraic circuits
We show improved lower bounds for constant depth algebraic circuits. This builds on the breakthrough work of Limaye, Srinavasan and Tavenas (FOCS 2021). We also show barriers to improving the lower bound further using the same techniques. This calls for new methods to obtain stronger bounds.

Vishwas Bhargava [video]
Linear Independence, Alternants, and Applications
In this talk, we will discuss a new technique for analyzing the linear independence of multivariate polynomials. At the core is a "Small Witness for Linear Independence" lemma, which states the following. If the polynomials f_{1}, f_{2}, ..., f_{k} \in \F[X] over X={x_{1}, ..., x_{n}} are \Flinearly independent then there exists a subset S \subseteq X of size at most k1 such that f_{1}, f_{2}, ..., f_{k} are also \F(X \setminus S)linearly independent.
An amalgamation of this structural result along with the alternant matrix gives us a criterion for testing linear independence. We will also discuss applications of this technique to the questions of polynomial identity testing.

Peter Bürgisser [slides] [video]
Zeros of structured polynomials over the reals and padics
Koiran's real tau conjecture claims that the number of real zeros of a univariate polynomial, computed by a depth four arithmetic circuit, is bounded by a polynomial in the size of the circuit. The real tau conjecture implies the separation of VP from VNP. We showed that random univariate polynomials typically have as few real zeros as predicted by the real tau conjecture. We propose to investigate a version of the tau conjecture concerned with padic zeros, since this would imply the separation of VP ne VNP as well. We note that, typically, there are much less padic zeros then real ones. For instance, a random sparse univariate polynomial on expectation has at most one padic zero! Recently, we arrived at a quite satisfactory understanding of the expected number of padic zeros of random fewnomial systems in terms of their Newton polytope. The situation looks much simpler than over the reals! We hope this will motivate work on the padic tauconjecture.

Abhranil Chatterjee [slides] [video]
Blackbox Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomialtime
Hrubeš and Wigderson (2015) initiated the complexitytheoretic study of noncommutative arithmetic formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative formula with inverses computes zero in the free skew field, equivalently whether there exists a nonzero matrix evaluation for the input formula. In the whitebox setting, there are deterministic polynomialtime algorithms due to Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018).
A central open problem in this area is to design an efficient deterministic blackbox identity testing algorithm for such formulas. In this talk, I'll present our recent work that solves this problem for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomialtime blackbox RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction.
It is joint work with V. Arvind (IMSc) and Partha Mukhopadhyay (CMI) accepted at RANDOM(2022).
The full version is available at https://eccc.weizmann.ac.il/report/2022/067/.

Prerona Chatterjee [slides] [video]
Lower bounds against noncommutative models of algebraic computation
Algebraic circuits are directed acyclic graphs where the leaves are labelled by variables or field constants, and internal nodes are labelled by addition (+) or multiplication (x). Therefore, each gate in the circuit naturally computes polynomials over the base field. In this talk, we will further assume that the multiplication gate is "noncommutative", and the question of interest will be to prove lower bounds against this model for some "explicit" polynomial. Although a lot of progress has been made towards this question in restricted settings, the best lower bound against general noncommutative circuits remains Ω(n log n) due to Baur and Strassen. In this talk, we will see some new lower bounds against noncommutative circuits under the additional assumption of "homogenity". In particular, we will prove that any homogeneous noncommutative circuit computing the ordered version of the elementary symmetric polynomial over n variables of degree n/2 must have size Ω(n^{2}), thus improving upon the lower bound due to Baur and Strassen. The talk is based on joint work with Pavel Hrubes (https://arxiv.org/abs/2301.01676).

Suryajith Chillara [slides] [video]
Algebraic circuit size lower bounds for restricted circuits, in a functional setting
We say that an arithmetic/algebraic circuit computes a polynomial if it can syntactically be generated from variables and field constants using algebraic operations + and x. Further, we say that an arithmetic circuit functionally computes (either over the entire domain, or a subdomain) a polynomial if the evaluation table, over a suitable evaluation space, of the circuit and the polynomial are equivalent.
In this talk, we are interested in understanding the bounds of functionally computing some polynomials of interest, by arithmetic circuits. The motivation for such consideration stems from the connection between Boolean and Algebraic complexity classes (cf. Forbes, Kumar and Saptharishi [CCC, 2016] and Bürgisser [TCS, 2000]). We shall first introduce and briefly survey the known circuit size lower bounds in the functional setting, then present the recent attempts at proving Boolean function lower bounds through algebraic circuit lower bounds, and then finally talk about open problems in this area.
The talk will loosely be based on the following work: https://drops.dagstuhl.de/opus/volltexte/2021/15525/pdf/LIPIcsFSTTCS202114.pdf

Nathaniel Aaron Collins [slides] [video]
CountFree WeisfeilerLeman and Group Isomorphism
In this paper, we investigate the power of counting in Group Isomorphism. We first leverage the countfree variant of the WeisfeilerLeman Version I algorithm for groups (Bracther & Schweitzer, LICS 2020) in tandem with limited nondeterminism and limited counting to improve the parallel complexity of isomorphism testing for several families of groups. In particular, we exhibit β_{1}MAC_{0}(FOLL) bounds
for several families of groups, including the following:
Let G_{1} and G_{2} be class 2 pgroups of exponent p arising from the CFI and twisted CFI graphs (Cai, Fürer, & Immerman, Combinatorica 1992) respectively, via Mekler's construction (J. Symb. Log., 1981). If the base graph Γ_{0} is 3regular and connected, then we can distinguish G_{1} from G_{2} in β_{1}MAC_{0}(FOLL). This improves the upper bound of TC^{1} from Brachter & Schweitzer (LICS 2020).
Isomorphism testing between an arbitrary group K and a group G with an Abelian normal Hall subgroup whose complement is either (i) O(1)generated solvable, or (ii) a finite simple group. This problem was previously known to be in P (Qiao, Sarma, & Tang, STACS 2011) and L (Grochow & Levet, arXiv 2022). Isomorphism testing between a direct product of simple groups and an arbitrary group. This problem was previously shown to be in
L (Brachter & Schweitzer, ESA 2022).
We finally show that the qary countfree pebble game is unable to distinguish even Abelian groups. This extends the result of Grochow & Levet (arXiv 2022), who established the result in the case of q = 1. In other words, some counting appears necessary to place
Group Isomorphism into P.

Radu Curticapean
Immanants and their complexity
Immanants are matrix functionals that generalize determinants and permanents. Given an irreducible character χ_{λ} of S_{n} for some integer partition λ of n, the immanant associated with λ is a sumproduct over permutations π in S_{n}, much like the determinant, but with χ_{λ}(π) playing the role of sgn(π).
Hartmann showed in 1985 that immanants can be evaluated in polynomial time for signish characters: For a partition λ of n with s parts, let b(λ) := n  s count the boxes to the right of the first column in the Young diagram of λ. The immanant associated with λ can be evaluated in n^{O(b(λ))} time.
Since this initial result, complementing hardness results have been obtained for several families of immanants derived from partitions with unbounded b(λ). This includes permanents, immanants associated with hook characters, and other classes. In this talk, we complete the picture of hard immanant families: Under an assumption from parameterized algebraic complexity, we rule out polynomialsized circuits for immanant families with unbounded b(λ). For immanant families in which b(λ) even grows polynomially, we establish hardness for VNP.
See arXiv:2102.04340.

Harm Derksen [video]
Orbit Problems
Given a group G and two vectors v and w in a representation V, one can ask: do v and w lie in the same orbit? This is what we call the orbit problem. For the action of GL(n) on mtuples of n x n matrices,
the orbit problem translates to the module isomorphism problem for which there is a known polynomial time algorithm. In joint work with Visu Makam, we also gave a polynomial time algorithm
for deciding whether the orbit closures of v and w intersect. We also have similar results for the leftright action of SL(n) x SL(n) on the space of mtuples of matrices. These results are related to interesting
problems in algebraic complexity theory, such as noncommutative rational identity testing. The graph isomorphism problem can also formulated as an orbit problem. No polynomial time algorithm
for the graph isomorphism problem is known. I will discuss an algorithm for the graph isomorphism problem that is more powerful than the higher dimensional WeisfeilerLeman algorithm when it comes
to distinguishing pairs of nonisomorphic graphs in polynomial time. (This algorithm could potentially be polynomial time, but we will not make such a bold claim.)

Prateek Dwivedi [video]
Deterministic identity testing paradigms for bounded topfanin depth 4 circuits
Deterministically solving the Polynomial Identity Testing (PIT) problem is a fundamental computational problem, and it is of pivotal importance in Algebraic Complexity Theory. This intrinsically difficult problem has found its way into many areas of Computer Science. In this talk, we will introduce the problem from the perspective of Algebraic Complexity Theory, discuss its motivations and connections.
Despite decades of effort, there has been little progress on the problem in general. Moreover, under strong restrictions on the circuits, we already have very efficient algorithms. One such wellmotivated restriction we consider is depth4 circuits. Special cases of these circuits are a great source of inspiration for ideas of designing PIT algorithms. However, their inapplicability led us to examine from a different viewpoint. In the talk, we will share these ideas, which helped us in designing efficient algorithms. Further, we will exhibit our newly developed paradigm for designing PIT algorithms.
The results in this talk are a joint work with Pranjal Dutta (CMI & IIT Kanpur) and Nitin Saxena (IIT Kanpur). They appeared in CCC 2021.

Alhussein Fawzi [video]
Discovering matrix multiplication algorithms with deep reinforcement learning
Improving the efficiency of algorithms for fundamental computational tasks such as matrix multiplication can have widespread impact, as it affects the overall speed of a large amount of computations. In this talk I will present AlphaTensor, our reinforcement learning agent based on AlphaZero for discovering efficient and provably correct algorithms for the multiplication of matrices. Using this approach, we find new algorithms outperforming the best ranks for many matrix sizes. I will describe how to formulate this problem as a singleplayer game, and the key machine learning ingredients that enable tackling difficult mathematical problems using reinforcement learning. This is based on https://www.nature.com/articles/s41586022051724.

Fulvio Gesmundo [slides] [video]
Border rank and homogeneous complexity classes
Recently, Kumar proved that any polynomial f can be approximated arbitrarily well by restrictions of the polynomial x_{1} ... x_{n}  1 for n large enough. In recent work with Dutta, Ikenmeyer, Jindal and Lysikov, we showed that, in the homogeneous setting, the minimal n for which this is possibly is strongly related to the border Waring rank of the polynomial f. Moreover, in the spirit of Kumar's result, we generalized this construction introducing a new polynomial which defines a subclass of the complexity class VBP, equivalent to VBP up to quasipolynomial blowup. In this talk, I will illustrate these results, highlighting connections to geometry and representation theory.

Utsab Ghosal [slides] [video]
Monotone Complexity of Spanning Tree Polynomial Revisited
We prove two results regarding the monotone complexity of the spanning tree polynomial, a classic VP polynomial in algebraic complexity theory.
Our first result shows a strongly exponential monotone lower bound against the Spanning tree polynomial defined over a constant degree expander graph. This gives the first strongly exponential monotone lower bound against a polynomial family in VP.
Recently, Hrubeš [H20] initiated a program to prove lower bounds against general arithmetic circuits by proving εsensitive lower bounds for monotone arithmetic circuits for a specific range of values for ε \in (0,1). The first εsensitive lower bound was proved for a family of polynomials inside VNP by [CDM21]. In this work we show an exponential size εsensitive lower bound against the Spanning tree polynomial defined over a complete graph.
This lower bound is obtained by showing a connection between Communication Complexity and Algebraic Complexity.
Authors : Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal and Partha Mukhopadhyay

Tom Gur [slides] [video]
An additive combinatorics approach to averagecase complexity
A recent line of work introduced a new technique that relies on Bogolyubov's lemma and the quasipolynomial BogolyubovRuzsa lemma to prove worstcase to averagecase reductions both in the classical and quantum settings. This talk will abstract the framework in an algebraic way and provide a crash course into the method, as well as a glimpse into upcoming results.

Neeraj Kayal [slides] [video]
Applications of Algebraic Complexity to Unsupervised Learning
We formulate an abstract computational problem called Robust Vector Space Decomposition and give
an efficient algorithm for it. This abstract problem provides a single framework that captures a wide
variety of learning problems, including the wellstudied problems of learning mixtures of Gaussians, tensor
decomposition, subspace clustering, and robust reconstruction of various classes of arithmetic formulas.
The problem is formally described as follows: Let U = U_{1} \oplus ... \oplus U_{r} and V = V_{1} \oplus ... \oplus V_{r} be vector
spaces, and suppose B is a space of linear operators from U to V, such that each U_{i} is mapped to V_{i} under
the action of B. Then, given the spaces U,V, and B approximately, the goal is to find (upto reordering) the
vector spaces U_{1}, ... ,U_{r}, V_{1}, ... ,V_{r} approximately.
We will see that the linear operators used to prove lower bounds for arithmetic formulas are also the ones that
can be used to reduce the above application problems to vector space decomposition.
The provable guarantees that we obtain on the goodness of our approximation relies on the smallest
nonzero singular values of certain linear operators being not too small. We conjecture that for smoothed instances
of our applications this is indeed the case, and hence, if true, the conjecture would imply that these problems admit efficient
algorithms in the smoothed setting.

Pascal Koiran [video]
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms
We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomized algorithm for the following problem: If a homogeneous polynomial f in K[x_{1},...,x_{n}] (where K \subseteq C) of degree d is given as a blackbox, decide whether it can be written as a linear combination of dth powers of linearly independent complex linear forms. The main novel features of the algorithm are:
(1) For d=3, we improve by a factor of n on the running time from an algorithm by Koiran and Skomra. The price to be paid for this improvement though is that the algorithm now has twosided error.
(2) For d>3, we provide the first randomized blackbox algorithm for this problem that runs in time polynomial in n and d (in an algebraic model where only arithmetic operations and equality tests are allowed). Previous algorithms for this problem as well as most of the existing reconstruction algorithms for other classes appeal to a polynomial factorization subroutine. This requires extraction of complex polynomial roots at unit cost and in standard models such as the unitcost RAM or the Turing machine this approach does not yield polynomial time algorithms.
(3) For d>3, when f has rational coefficients, the running time of the blackbox algorithm is polynomial in n,d and the maximal bit size of any coefficient of f. This yields the first algorithm for this problem over C with polynomial running time in the bit model of computation.
See https://arxiv.org/abs/2110.05305
This also serves as an introduction to Subhayan Saha's talk.

Mrinal Kumar [slides] [video]
Fast multivariate multipoint evaluation
Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. A straightforward algorithm for this problem is to just iteratively evaluate the polynomial at each of the inputs. The question of obtaining fasterthannaive (and ideally, close to linear time) algorithms for this problem is a natural and fundamental question in computational algebra. In addition to its own inherent interest, faster algorithms for multipoint evaluation are closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition.
In this talk, I will briefly survey the state of art for this problem, and mention some recent improvements and applications.

Benjamin Lovitz [slides] [video]
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
We study the problem of finding elements in the intersection of an arbitrary conic variety in F^{n} with a given linear subspace (where F can be the real or complex field). This problem captures a rich family of algorithmic problems under different choices of the variety. The special case of the variety consisting of rank1 matrices already has strong connections to central problems in different areas like quantum information theory and tensor decompositions. This problem is known to be NPhard in the worstcase, even for the variety of rank1 matrices.
Surprisingly, despite these hardness results we give efficient algorithms that solve this problem for "typical" subspaces. Here, the subspace U\subseteq F^{n} is chosen generically of a certain dimension, potentially with some generic elements of the variety contained in it. Our main algorithmic result is a polynomial time algorithm that recovers all the elements of U that lie in the variety, under some mild nondegeneracy assumptions on the variety. As corollaries, we obtain the following results:
 Uniqueness results and polynomial time algorithms for generic instances of a broad class of lowrank decomposition problems that go beyond tensor decompositions. Here, we recover a decomposition of the form Σ_{i} v_{i} \otimes w_{i}, where the v_{i} are elements of the given variety X. This implies new algorithmic results even in the special case of tensor decompositions.
 Polynomial time algorithms for several entangled subspaces problems in quantum entanglement, including determining rentanglement, complete entanglement, and genuine entanglement of a subspace. While all of these problems are NPhard in the worst case, our algorithm solves them in polynomial time for generic subspaces of dimension up to a constant multiple of the maximum possible.
This is based on joint work with Nathaniel Johnston and Aravindan Vijayaraghavan https://arxiv.org/abs/2212.03851

Vladimir Lysikov [slides] [video]
Degreerestricted strength decompositions and algebraic branching programs
We analyze Kumar's recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that gives better bounds in some cases.
The lower bound relies on NoetherLefschetz type conditions on the hypersurface defined by the homogeneous polynomial. In the explicit example that we provide, the lower bound is proved resorting to classical intersection theory.
Furthermore, we use similar methods to improve the known lower bound methods for slice rank of polynomials. We consider a sequence of polynomials that have been studied before by Shioda and show that for these polynomials the improved lower bound matches the known upper bound.
This is joint work with Fulvio Gesmundo, Purnata Ghosal, and Christian Ikenmeyer: https://arxiv.org/abs/2205.02149.

Visu Makam [video]
Singular tuples of matrices is not a null cone
The following multideterminantal algebraic variety plays a central role in algebra,
algebraic geometry and computational complexity theory: SING(n,m), consisting of all mtuples of n x n complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING(n,m) will imply superpolynomial circuit lower bounds, a holy grail of the theory of computation.
A sequence of recent works suggests such efficient algorithms for memberships in a general class of algebraic varieties, namely the null cones of linear group actions. Can this be used for the problem above? Our main result is negative: SING(n,m) is not the null cone of any (reductive) group action! This stands in stark contrast to a noncommutative analog of this variety, and points to an inherent structural difficulty of SING(n,m).
To prove this result we identify precisely the group of symmetries of SINGn,m. We find this characterization, and the tools we introduce to prove it, of independent interest. Our work significantly generalizes a result of Frobenius for the special case m = 1, and suggests a general method for determining the symmetries of algebraic varieties.

Chandra Kanta Mohapatra [slides] [video]
Schur polynomials do not have small formulas if the determinant does not
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric functions, in Representation theory.
However, unlike some other families of symmetric polynomials like the Elementary Symmetric polynomials, the Power Symmetric polynomials and the Complete Homogeneous Symmetric polynomials, the computational complexity of syntactically computing Schur polynomials has not been studied much. In particular, it is not known whether Schur polynomials can be computed efficiently by algebraic formulas. In this work, we address this question, and show that unless every polynomial with a small algebraic branching program (ABP) has a small algebraic formula, there are Schur polynomials that cannot be computed by algebraic formula of polynomial size. In other words, unless the algebraic complexity class VBP is equal to the complexity class VF, there exist Schur polynomials which do not have polynomial size algebraic formulas.
As a consequence of our proof, we also show that computing the determinant of certain generalized Vandermonde matrices is essentially as hard as computing the general symbolic determinant. To the best of our knowledge, these are one of the first hardness results of this kind for families of polynomials which are not multilinear. A key ingredient of our proof is the study of composition of well behaved algebraically independent polynomials with a homogeneous polynomial, and might be of independent interest.

Jakob Moosbauer [slides] [video]
Flip Graphs for Matrix Multiplication
The cost of matrix multiplication remains one of the big open questions in algebraic complexity
theory. In 1969 Strassen discovered a multiplication scheme that computes the product of two 2x2
matrices using only 7 multiplications in the ground ring. Such multiplication schemes give rise to
multiplication algorithms for arbitrary matrices. In this talk we will present a method for
discovering new matrix multiplication schemes based on random walks in a certain graph which we call
the flip graph. The vertices of this graph are matrix multiplication schemes and the edges
represent transformations from one scheme to another. During a random walk we can encounter schemes
which allow one multiplication to be eliminated. Using this method we are able to reduce the number
of multiplications for the matrix formats <4,4,5> and <5,5,5>, both in characteristic two and for
arbitrary ground rings.

Seyed Sajjad Nezhadi [slides] [video]
Compression of nonlocal games
Recently, works such as the landmark MIP*=RE paper by Ji et. al. as well as our paper on "Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy" have established deep connections between computability theory and the power of nonlocal games with entangled provers. These works start by establishing compression procedures for nonlocal games, which exponentially reduce the verifier's computational task during a game. These compression procedures are then used to construct reductions from uncomputable languages to nonlocal games, by a technique known as iterated compression.
In this talk, I will give an overview of the compression scheme and demonstrate how it can be used to perform reductions. I will then quickly discuss some of the algebraic ingredients involved in performing compression such as selftesting and introspection.

Youming Qiao [slides] [video]
Some algebraic algorithms and complexity classes inspired by connections between graphs and matrix spaces
Linear spaces of matrices, or matrix spaces, appear naturally in the study of polynomial identity testing and group isomorphism. In this talk, we examine connections between graphs and matrix spaces, the first of which goes back to the works of Tutte, Edmonds, and Lovász. These connections provide a useful viewpoint on some algebraic algorithms and complexity classes, such as algorithms for the noncommutative rank problem and the group isomorphism problem, and the TensorIsomorphism complexity class. Such connections also lead to new questions in algebraic complexity, such as testing whether a matrix space contains only nilpotent matrices.

Roshan Raj [slides] [video]
Border Complexity of Symbolic Determinant under Rank One Restriction
VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of form A_{0} + \sum_{i=1}^n A_{i} x_{i} where the size of each A_i is polynomial in the number of variables (equivalently, computable by polynomialsized algebraic branching programs (ABP)). A major open problem in geometric complexity theory (GCT) is to determine whether VBP is closed under approximation. The power of approximation is well understood for some restricted models of computation, e.g. the class of depthtwo circuits, readonce ABPs (ROABP), monotone ABPs, depththree circuits of bounded top fanin, and widthtwo ABPs. The former three classes are known to be closed under approximation [Bläser, Ikenmeyer, Mahajan, Pandey, and Saurabh (2020)], whereas the approximative closure of the last one captures the entire class of polynomial families computable by polynomialsized formulas [Bringmann, Ikenmeyer, and Zuiddam (2017)].
We consider the subclass of VBP computed by the determinant of a symbolic matrix of form A_{0} + \sum_{i=1}^n A_{i} x_{i} where each A_{i} a rank one matrix. This class has been studied extensively [Edmonds(1968), Edmonds(1979)] and efficient identity testing algorithms are known for it [Lovasz (1989), Gurjar and Thierauf (2020)]. We show that this class is closed under approximation.
This talk is based on a joint work with Abhranil Chatterjee, Sumanta Ghosh and Rohit Gurjar

Subhayan Saha [slides] [video]
Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
We study symmetric tensor decompositions, i.e. decompositions of the input symmetric tensor T of order 3 as sum of r 3rdorder tensor powers of u_{i} where u_{i} are vectors in \C^{n}. In order to obtain efficient decomposition algorithms, it is necessary to require additional properties from the u_{i}. In this paper we assume that the u_{i} are linearly independent. This implies that r is at most n, i.e., the decomposition of T is undercomplete. We will moreover assume that r=n (we plan to extend this work to the case where r is strictly less than n in a forthcoming paper). We give a randomized algorithm for the following problem: given T, an accuracy parameter epsilon, and an upper bound B on the condition number of the tensor, output vectors u'_{i} such that u_{i} and u'_{i} differ by at most epsilon (in the l_{2} norm and up to permutation and multiplication by phases) with high probability. The main novel features of our algorithm are: (1) We provide the first algorithm for this problem that works in the computation model of finite arithmetic and requires only polylogarithmic (in n, B and 1/epsilon) many bits of precision. (2) Moreover, this is also the first algorithm that runs in linear time in the size of the input tensor. It requires O(n^{3}) arithmetic operations for all accuracy parameters epsilon = 1/poly(n).
Joint work with Pascal Koiran and the preprint is available at (https://arxiv.org/abs/2211.07407)

Shubhangi Saraf [video]
NearOptimal Lower Bounds for SetMultilinear Formulas
The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for setmultilinear formulas.
In this talk, along with discussing the impact of these work and several others in the literature, I will discuss some new results in this area, namely strong and nearoptimal lower bounds for setmultilinear circuits/formulas in the constant (or low) depth setting, as well as the unbounded depth setting.
This is based on joint work with Deepanshu Kush.

Nitin Saurabh [slides] [video]
Rabbits approximate, Cows compute exactly!
Valiant, in his seminal paper in 1979, showed an efficient simulation of algebraic formulas by determinants,
showing that VF, the class of polynomial families computable by polynomialsized algebraic formulas, is contained in VDet,
the class of polynomial families computable by polynomialsized determinants.
Whether this containment is strict has been a longstanding open problem.
It is thus natural to ask what is the simplest class of matrices whose determinants exactly capture algebraic formulas?
In this talk I will give an answer to the above question and, of course, explain the title!
This is based on a joint work with Balagopal Komarath (IIT Gandhinagar) and Anurag Pandey (IIT Madras).

Nitin Saxena [slides] [video]
Demystifying the border of depth3 algebraic circuits
Border (or approximative) complexity of polynomials plays an integral role in GCT approach to P!=NP. This raises an important open question: can a border circuit be *efficiently* debordered (i.e. convert from approximative to exact)? Or, could the approximation involve exponentialprecision which may not be efficiently simulable? Circuits of depth 3 or 4, are a good testing ground for this question.
Kumar (ToCT'20) proved the universal power of the border of topfanin2 depth3 circuits. We recently solved some of the related open questions. In this talk we will outline our result:
border of boundedtopfanin depth3 circuits is relatively easy it can be computed by a polynomialsize algebraic branching program (ABP). Our debordering paradigm has many applications, especially in identity testing and lower bounds.
Based on the works with Prateek Dwivedi & Pranjal Dutta (CCC 2021) + (FOCS 2021, invited to SICOMP) + (FOCS 2022).
[https://www.cse.iitk.ac.in/users/nitin/research.html]

Amir Shpilka [slides] [video]
Points, lines and polynomial identities
The SylvesterGallai (SG) theorem in discrete geometry asserts that if a finite set of points P has the property that every line through any two of its points intersects the set at a third point, then P must lie on a line. Surprisingly, this theorem, and some variants of it, appear in the analysis of locally correctable codes and, more noticeably, in polynomial identity testing. For these questions one often has to study extensions of the original SG problem: the case where there are several sets, or with a robust version of the condition (many "special" lines through each point) or with a higher degree analog of the problem, etc.
In this talk I will present the SG theorem and some of its variants, show its relation to the abovementioned problems and discuss recent developments regarding higher degree analogs and their applications.

Amit Kumar Sinhababu [slides] [video]
Factorization, root finding, and several other things
Given a blackbox computing a product of some constant degree polynomials over rationals, we show how to output these factors
in deterministic polynomial time. Besides this, we present the state of the art on the closure of algebraic complexity classes
under factoring, and connections of special cases of multivariate factoring with specific questions in PIT.
Joint work with Pranjal Dutta and Thomas Thierauf.

KV Subrahmanyam [slides] [video]
Towards refining the no obstruction conjecture in GCT
Let perm_{m} denote the permanent of an m x m matrix with indeterminates x_{ij}. Let n > m and let y=det_{n} denote the determinant of an n x n matrix with indeterminates x_{ij} with stabilizer K \subseteq G:=GL(n^{2}). Geometric Complexity Theory [Mulmuley, Sohoni, 01, 08] suggests one approach to proving lower bounds on the determinantal complexity of perm_{m}  show that the padded permanent z=x_{nn}^{nm}perm_{m}, with stabilizer H, is not in the Gorbit closure of det_{n} unless n is exponential in m. The No Occurrence obstruction was based on the resulting surjection A_{y} \rightarrow A_{z} of the corresponding coordinate rings, and conjectured that the information on the stabilizers K and H would suffice to identify Gmodules in A_{z} which could not be present in A_{y}, when n is subexponential in m. This was disproved in two papers [Ikenmeyer, Panova, 17], [Bürgisser, Ikenmeyer, Panova 19]. We give a different, conceptual proof of why the conjecture fails using notions from GIT. Our proof requires no calculations. As pointed out by these and other authors, while the stabilizers K and H may indeed provide obstructions, this may need a more refined analysis of the occurrence and perhaps, multiplicities and locations of the Gmodules in A_{y} and A_{z}. We make some progress in two directions.
The general setting is that of a reductive group G acting linearly on a vector space V and therefore P(V). Let y, z be in V with stabilizers K, H respectively. Let t be an indeterminate and suppose λ(t) is a one parameter subgroup of G driving y to z in P(V), i.e. z is the leading term LT(y,λ) of λ(t)y.
We first show that λ(t) allows us to construct \hat{Lie(K)}, the leading term Lie algebra of the Lie algebra Lie(K) of K. Moreover, \hat{Lie(K)} \subseteq Lie(H) and has the same dimension as K. This offers a concrete computational connection between K and H. We show that under certain conditions, elements of Lie(K) are present in Lie(H).
Next, using λ(t) and the direction along which y approaches z we give two natural constructions of Gstable subvarieties W(λ) and O(Z_{d}) that are sandwiched between the orbit closure of y and the orbit closure of z. The construction of W(λ) allows a filtration of the kernel of the surjection A_{y} \rightarrow A_{z}. We describe these Gstable subvarieties in numerous examples, and show how studying these sandwich varieties could lead to nuanced versions of occurrence obstructions. This is joint work with Bharat Adsul and Milind Sohoni.

Sebastién Tavenas [video]
Approaching Lower Bounds for Algebraic Formulas
This talk will present recent advances in obtaining better lower bounds for algebraic formulas. We will discuss a parallelization technique that achieves logarithmic depth in the degree for small homogeneous formulas, which reduces the problem of obtaining lower bounds for general homogeneous formulas to that of small depth formulas. We will also explore how superpolynomial lower bounds can be obtained in the lowdegree and lowdepth regime by applying the partial derivative method to certain lopsided setmultilinear polynomials. These lower bounds will continue to be superpolynomial for formulas of depth at most O(log(log(d))). Finally, we will show that the best lower bound we can prove for setmultilinear formulas of productdepth D can be characterized in terms of the combinatorial properties of a specific multiset W of size d, referred to as the "depthD tree bias" of W.
This talk is based on joint work with Nutan Limaye, Srikanth Srinivasan, Hervé Fournier, and Guillaume Malod.

Anamay Tengse [slides] [video]
Sums of powers of linear forms, partial derivatives, and commuting matrices
Sums of powers of linear forms are quite an interesting model in algebraic circuit complexity. On the one hand, we have almosttight exponential lower bounds against this model. On the other hand, we do not yet know of polynomial time (blackbox) identity tests for it. All known identity tests use the fact that sums of `few' powers of linear forms have `small' dimensionofpartialderivatives. However, we do not have a good answer about the converse of this statement.
In this talk, we will see a rather surprising connection between the converse mentioned above, and sets of commuting matrices. As it turns out, this connection also brings yet another simplebutinteresting model into the picture: readonce (oblivious) ABPs. The hope is that this connection will help reveal new properties of both these models, and thus lead to some (much awaited) new results.
This talk is based on a joint work (arxiv.org/abs/2201.06432) with C. Ramya (IMSc, Chennai).

Dhara Thakkar [slides] [video]
On the universality of border width2 ABPs over characteristic 2
The celebrated result by BenOr and Cleve (SICOMP, 1992)
showed that formulas are polynomially equivalent to width3 ABPs,
i.e., VF=VBP_{3}. Further, there are simple
polynomials, such as, \sum_{i=1}^8 x_{2i1} \cdot x_{2i}, that cannot
be computed by width2 ABPs (CC, 2016). Bringmann, Ikenmeyer, and
Zuiddam (J.ACM, 2018) studied these questions in the approximative
(border complexity) setting and showed the universality of width2
ABPs, over fields of characteristics \ne 2. In particular, they
showed that polynomials that can be approximated arbitrarily closely
by formulas could also be approximated (with polynomial blowup in
size) by width2 ABPs, i.e.,
\overline{VF}=\overline{VBP}_{2}. They left open the
question over characteristic 2.
In this talk, we discuss the universality of
\overline{VBP}_{2}, even over characteristic 2. In
particular, we will prove that any ssparse, degreed polynomial
with \leq t indeterminates per monomial can be approximated by
O(s(d+2^{t}))size width2 ABPs. We will also discuss other related
results.
The talk is based on the joint work with Pranjal Dutta, Balagopal
Komarath, Harshil Mittal, and Saraswati Nanoti.

Chris Umans [video]
Matrix multiplication via matrix groups
Cohn and Umans proposed a grouptheoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining omega = 2, while other families of groups remain potentially viable. In this work we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored. We first show that finite groups of Lie type cannot prove omega = 2 within the grouptheoretic approach. This is based on a representationtheoretic argument that identifies the secondsmallest dimension of an irreducible representation of a group as a key parameter that determines its viability in this framework. Our proof builds on Gowers' result concerning productfree sets in quasirandom groups. We then give another barrier that rules out certain natural matrix group constructions that make use of subgroups that are far from being selfnormalizing. Our barrier results leave open several natural paths to obtain exponent 2 via matrix groups. To explore these routes we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of exponent 2 in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving omega = 2. We give constructions in the continuous setting, which evade our two barriers, and indeed are "bestpossible" in a precise sense. We then describe a new ingredient  "separating polynomials"  which allow us to recover a fullfledged framework yielding actual algorithms in the Lie setting (rather than constructions whose interest is only by analogy).

Jeroen Zuiddam [slides] [video]
The subrank of random tensors
The subrank of a tensor measures how much the tensor can be diagonalised. This notion was introduced by Strassen in 1987 to study matrix multiplication algorithms, and is related to several problems in combinatorics and quantum information. We determine the subrank of random tensors, establishing a large gap between the subrank on the one hand and the slice rank, analytic rank and geometric rank on the other hand. This is joint work with Derksen and Makam.
Previous WACTs
Organisers
Organised by Christian Ikenmeyer and the administrative staff of the Department of Computer Science and the Warwick Mathematics Institute, and Martin Lotz and Abhiram Natarajan.