7th Workshop on Algebraic Complexity Theory (WACT) 2023

Time and Place

• Monday 2023-March-27 to Friday 2023-March-31
• Lecture Hall CS1.04 in the Department of Computer Science, The University of Warwick, Coventry, UK

This is an on-site event. In the unlikely event that public health measures related to COVID-19 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)

• Harm Derksen (Northeastern University)

• Alhussein Fawzi (DeepMind London)

• Shubhangi Saraf (University of Toronto)

• Nitin Saxena (Indian Institute of Technology Kanpur)

• Amir Shpilka (Tel-Aviv University)

• Sébastien Tavenas (Laboratoire de Mathématiques, Université Savoie Mont Blanc)

• Youming Qiao (University of Technology Sydney)

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

	Mon 27	Tue 28	Wed 29	Thu 30	Fri 31	Sat 1
08:30-09:00	registration					Departure
09:00-09:30	plenary talk: Tavenas	plenary talk: Fawzi	plenary talk: Shpilka	Zuiddam	plenary talk: Derksen
09:30-10:00				Lovitz
10:00-10:30	coffee break / registration	coffee break	coffee break	coffee break	coffee break
10:30-11:00	Bhargav	Koiran	Sinhababu	plenary talk: Qiao	Makam
11:00-11:30	Subrahmanyam	Saha	Tengse		A. Chatterjee
11:30-12:00	coffee break	coffee break	coffee break	coffee break	coffee break
12:00-12:30	Lysikov	Bürgisser	Gesmundo	Nezhadi	P. Chatterjee
12:30-14:00	lunch at NAIC Café	lunch at NAIC Café	Group picture, then lunch at NAIC Café	lunch at NAIC Café	lunch at NAIC Café
14:00-14:30	plenary talk: Curticapean	Kumar	plenary talk: Saraf	plenary talk: Saxena	Raj
14:30-15:00		Mohapatra			Saurabh
15:00-15:30	coffee break	coffee break	break	coffee break	coffee break
15:30-16:00	Umans	Chillara	Light hike through the countryside, off-campus dinner at the Queen and Castle	Gur	Ghosal
16:00-16:30	Collins	Kayal		Dwivedi	Thakkar
16:30-17:00	Bhargava	Open problem session		Andrews	Moosbauer
17:00-17:30	Informal small group research			Informal small group research	Informal small group research
17:30-18:15		Informal small group research
18:30-19:30	dinner on campus at Radcliffe	dinner on campus at Radcliffe		dinner on campus at Radcliffe	dinner on campus at Radcliffe

Registration

Registration is closed.

Registered Participants

Robert Andrews (University of Illinois Urbana-Champaign), 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 Urbana-Champaign), 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 on-campus 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 Low-Rank Matrices
  Designing efficient deterministic algorithms for polynomial identity testing (PIT) is a central goal of algebraic complexity theory. For weak circuit classes, such as depth-three diagonal circuits and read-once 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 low-rank matrices as a hitting set. Because matrix rank is characterized by the non-vanishing of minors, it is natural to conjecture that low-rank matrices are a hitting set for circuit classes that cannot efficiently compute the determinant. By carefully analyzing the polynomials that vanish on low-rank matrices, we prove this conjecture for low-depth circuits and for formulas (conditioned on formula lower bounds for the determinant). This yields new hitting set generators with a near-optimal 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₁, f₂, ..., f_k \in \F[X] over X={x₁, ..., x_n} are \F-linearly independent then there exists a subset S \subseteq X of size at most k-1 such that f₁, f₂, ..., 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 p-adics
  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 p-adic zeros, since this would imply the separation of VP ne VNP as well. We note that, typically, there are much less p-adic zeros then real ones. For instance, a random sparse univariate polynomial on expectation has at most one p-adic zero! Recently, we arrived at a quite satisfactory understanding of the expected number of p-adic 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 p-adic tau-conjecture.
• Abhranil Chatterjee [slides] [video]
  Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time
  Hrubeš and Wigderson (2015) initiated the complexity-theoretic 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 white-box setting, there are deterministic polynomial-time 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 black-box 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 quasipolynomial-time black-box 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 non-commutative 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 "non-commutative", 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 non-commutative circuits remains Ω(n log n) due to Baur and Strassen. In this talk, we will see some new lower bounds against non-commutative circuits under the additional assumption of "homogenity". In particular, we will prove that any homogeneous non-commutative circuit computing the ordered version of the elementary symmetric polynomial over n variables of degree n/2 must have size Ω(n²), 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 sub-domain) 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/LIPIcs-FSTTCS-2021-14.pdf
• Nathaniel Aaron Collins [slides] [video]
  Count-Free Weisfeiler-Leman and Group Isomorphism
  In this paper, we investigate the power of counting in Group Isomorphism. We first leverage the count-free variant of the Weisfeiler-Leman Version I algorithm for groups (Bracther & Schweitzer, LICS 2020) in tandem with limited non-determinism and limited counting to improve the parallel complexity of isomorphism testing for several families of groups. In particular, we exhibit β₁MAC₀(FOLL) bounds for several families of groups, including the following: Let G₁ and G₂ be class 2 p-groups 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 Γ₀ is 3-regular and connected, then we can distinguish G₁ from G₂ in β₁MAC₀(FOLL). This improves the upper bound of TC¹ 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 q-ary count-free 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 sum-product 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 sign-ish 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 polynomial-sized 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 m-tuples 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 left-right action of SL(n) x SL(n) on the space of m-tuples of matrices. These results are related to interesting problems in algebraic complexity theory, such as non-commutative 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 Weisfeiler-Leman algorithm when it comes to distinguishing pairs of non-isomorphic 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 top-fanin 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 well-motivated restriction we consider is depth-4 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 single-player 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/s41586-022-05172-4.
• 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₁ ... 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 quasi-polynomial blow-up. 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 Re-visited
  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 average-case complexity
  A recent line of work introduced a new technique that relies on Bogolyubov's lemma and the quasi-polynomial Bogolyubov-Ruzsa lemma to prove worst-case to average-case 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 well-studied 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₁ \oplus ... \oplus U_r and V = V₁ \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₁, ... ,U_r, V₁, ... ,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 non-zero 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₁,...,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 d-th 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 two-sided 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 unit-cost 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 faster-than-naive (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ⁿ 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 rank-1 matrices already has strong connections to central problems in different areas like quantum information theory and tensor decompositions. This problem is known to be NP-hard in the worst-case, even for the variety of rank-1 matrices. Surprisingly, despite these hardness results we give efficient algorithms that solve this problem for "typical" subspaces. Here, the subspace U\subseteq Fⁿ 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 non-degeneracy 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 low-rank 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 r-entanglement, complete entanglement, and genuine entanglement of a subspace. While all of these problems are NP-hard 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]
  Degree-restricted 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 Noether-Lefschetz 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 multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: SING(n,m), consisting of all m-tuples 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 super-polynomial 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 non-commutative 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 self-testing 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 non-commutative rank problem and the group isomorphism problem, and the Tensor-Isomorphism 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₀ + \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 polynomial-sized 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 depth-two circuits, read-once ABPs (ROABP), monotone ABPs, depth-three circuits of bounded top fan-in, and width-two 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 polynomial-sized formulas [Bringmann, Ikenmeyer, and Zuiddam (2017)].
  We consider the subclass of VBP computed by the determinant of a symbolic matrix of form A₀ + \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 3rd-order tensor powers of u_i where u_i are vectors in \Cⁿ. 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₂ 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 poly-logarithmic (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³) 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]
  Near-Optimal Lower Bounds for Set-Multilinear 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 set-multilinear 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 near-optimal lower bounds for set-multilinear 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 polynomial-sized algebraic formulas, is contained in VDet, the class of polynomial families computable by polynomial-sized determinants. Whether this containment is strict has been a long-standing 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 depth-3 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 exponential-precision 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 top-fanin-2 depth-3 circuits. We recently solved some of the related open questions. In this talk we will outline our result: border of bounded-top-fanin depth-3 circuits is relatively easy- it can be computed by a polynomial-size algebraic branching program (ABP). Our de-bordering 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 Sylvester-Gallai (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 above-mentioned 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 black-box 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²). 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^{n-m}perm_m, with stabilizer H, is not in the G-orbit 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 G-modules 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 G-modules 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 G-stable 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 G-stable 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 low-degree and low-depth regime by applying the partial derivative method to certain lopsided set-multilinear 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 set-multilinear formulas of product-depth D can be characterized in terms of the combinatorial properties of a specific multi-set W of size d, referred to as the "depth-D 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 almost-tight 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' dimension-of-partial-derivatives. 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 simple-but-interesting model into the picture: read-once (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 width-2 ABPs over characteristic 2
  The celebrated result by Ben-Or and Cleve (SICOMP, 1992) showed that formulas are polynomially equivalent to width-3 ABPs, i.e., VF=VBP₃. Further, there are simple polynomials, such as, \sum_{i=1}^8 x_2i-1 \cdot x_2i, that cannot be computed by width-2 ABPs (CC, 2016). Bringmann, Ikenmeyer, and Zuiddam (J.ACM, 2018) studied these questions in the approximative (border complexity) setting and showed the universality of width-2 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 width-2 ABPs, i.e., \overline{VF}=\overline{VBP}₂. They left open the question over characteristic 2.
  In this talk, we discuss the universality of \overline{VBP}₂, even over characteristic 2. In particular, we will prove that any s-sparse, degree-d polynomial with \leq t indeterminates per monomial can be approximated by O(s(d+2^t))-size width-2 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 group-theoretic 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 group-theoretic approach. This is based on a representation-theoretic argument that identifies the second-smallest 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 product-free 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 self-normalizing. 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 "best-possible" in a precise sense. We then describe a new ingredient -- "separating polynomials" -- which allow us to recover a full-fledged 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

• WACT 2019 (ICTS Bangalore)
• WACT 2018 (Université Paris Diderot)
• WACT 2016 (Tel Aviv University)
• WACT 2015 (Saarbrücken)
• WACT 2014 (Saarbrücken)
• WACT 2013 (Aarhus University)

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.