All the talks are available on this YouTube channel.
Speaker: Avi Wigderson
Title: Permanent & Determinant: non-identical twins
Abstract: The Determinant is undoubtedly the most important polynomial function in mathematics. Its lesser-known sibling, the Permanent, plays very important roles in enumerative combinatorics, statistical and quantum physics, and the theory of computation. In this lecture, I plan to survey some of the many remarkable properties of the permanent, its applications and impact on fundamental computational problems, its similarities to and apparent differences from the determinant, and how these relate to the P vs. NP problem.
This lecture is intended for a general Math & CS audience.
[Slides] [Video]
Speaker: Rahul Santhanam
Title: Meta-Mathematics of Algebraic Complexity
Abstract: We initiate the study of the meta-mathematics of algebraic circuit lower bounds. We show several upper and lower bounds on the provability of algebraic circuit lower bounds. We show unconditionally that algebraic circuit lower bounds are hard for weak proof systems such as Polynomial Calculus with Reasoning (PCR). We also give evidence that the constant-depth algebraic circuit lower bounds of Limaye-Srinivasan-Tavenas (LST) and Forbes are unlikely to be provable within constant-depth IPS. In terms of upper bounds, we show that the LST and Forbes lower bounds can be established with quasipolynomial-size Frege proofs.
This is based on joint work with Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu and Iddo Tzameret.
[Slides] [Video]
Speaker: Robert Andrews
Title: Hilbert’s Nullstellensatz is in the Counting Hierarchy
Abstract: We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, lies in the counting hierarchy. More generally, we show that the number of solutions to a system of equations can be computed in polynomial time with oracle access to the counting hierarchy. Our results hold in particular for polynomials with coefficients in either the rational numbers or a finite field. Previously, the best-known bounds on the complexities of these problems were PSPACE and FPSPACE, respectively. Our main technical contribution is the construction of a uniform family of constant-depth arithmetic circuits that compute the multivariate resultant. Joint work with Abhibhav Garg and Éric Schost.
[Slides] [Video]
Speaker: Sanyam Agarwal
Title: Nullstellensätze for Approximate Polynomial Satisfiability
Abstract: Guo, Saxena, and Sinhababu (TOC'18, CCC'18) defined a natural, approximative analog of the polynomial system satisfiability problem, which they called approximate polynomial satisfiability (APS). They proved algebraic and geometric properties of it and showed an NP-hardness lower bound and a PSPACE upper bound for it. They further established how the problem naturally occurs in border complexity and Geometric complexity theory (GCT) and used the problem to construct hitting sets for VP in PSPACE, hence greatly mitigating the GCT chasm.
In this talk, I will talk about how their criterion for non-existence of approximative solutions can be interpreted as an analog of Weak Hilbert's Nullstellensatz in the approximative setting. I will then discuss how we can derive a strong analog of this Nullstellensatz in the approximative setting and how it relates to some well studied concepts in commutative algebra. Finally, I discuss how we can show a matching PSPACE upper bound for this Nullstellensatz, coinciding with the matching complexity of the strong and weak Nullstellensatz in the classical setting.
This is based on joint work with Sagnik Dutta, Anurag Pandey, and Himanshu Shukla.
[Slides] [Video]
Speaker: Igor Pak
Title: Complexity of vanishing of structure coefficients
Abstract: I will give a short overview of the complexity problems of the vanishing of various structure constants. I will then discuss our recent result that the vanishing of Schubert coefficients can be decided in probabilistic polynomial time via polynomial identity testing. Joint work with Colleen Robichaux.
[Slides] [Video]
Speaker: Ian Orzel
Title: Is the Circuit Complexity of Set-Multilinear Polynomials Submultiplicative over Kronecker Products?
Abstract: Set-multilinear polynomials are an important class of polynomials that share a close relationship with tensors. Tensor rank, a generalization of matrix rank to tensors, is the foundation of many open problems in computer science.
The study of this quantity leads to a natural definition of "multiplication" of tensors through the Kronecker product operation, over which tensor rank is submultiplicative. This product is also defined for set-multilinear polynomials.
Strassen showed that tensor rank and circuit complexity coincide asymptotically for set-multilinear polynomials of degree d=3, or 3-mode tensors. It follows that circuit complexity is submultiplicative for d=3. No such results are known for d >= 4.
In this talk, I will show that submultiplicativity is unlikely for higher degrees, as it would refute standard assumptions:
Strong submultiplicativity would imply VP = VNP, and slightly weakened assumptions would produce sub-2^n circuits for the permanent and proofs that \omega = 2, where \omega is the matrix-multiplication exponent.
Our proofs rely on so-called "graph tensors", zero-one tensors built from graphs, where each vertex corresponds to a variable set. These enable us to use graph-theoretic arguments to obtain a proof of Strassen's 2\omega/3 upper bound on the asymptotic rank exponent of 3-mode tensors, including an extension to a (d-1)\omega/3 upper bound for d-mode tensors.
Using these techniques, we give state-of-the-art bounds for the asymptotic rank exponent when d >= 4, as well as new upper bounds for the corresponding asymptotic exponent of circuit complexity when d >= 4 is small.
The talk is based on joint work with Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Tim Seppelt, and Jiaheng Wang.
Speaker: Pascal Koiran
Title: Tensor decomposition beyond uniqueness, with an application to the minrank problem
Abstract: We prove a generalization to Jennrich's uniqueness theorem for tensor decompositions in the undercomplete setting. Our uniqueness theorem is based on an alternative definition of the standard tensor decomposition, which we call matrix-vector decomposition. Moreover, in the same settings in which our uniqueness theorem applies, we also design and analyze an efficient randomized algorithm to compute the unique minimum matrix-vector decomposition (and thus a tensor rank decomposition of minimum rank).
As an application of our uniqueness theorem and our efficient algorithm, we show how to compute all matrices of minimum rank (up to scalar multiples) in certain generic vector spaces of matrices. Joint work with Rafael Oliveira.
[Slides] [Video]
Speaker: Jeong-Hoon Ju
Title: On the Ranks of the Determinant and Permanent Tensors
Abstract: In algebraic complexity theory, there have been many attempts to compare the determinant and permanent polynomials in terms of determinantal complexity and border determinantal complexity. From a tensorial viewpoint, the determinant is a skew-symmetric tensor and the permanent is a symmetric tensor. In this talk, we investigate the tensor rank and border rank of the determinant and permanent tensors. In particular, we establish a separation between the determinant and permanent tensors with respect to tensor rank and border rank by improving the lower bound for the border rank of the determinant tensor. The main tool for improving the lower bound is the recursive Koszul flattening, originally proposed by Hauenstein-Oeding-Ottaviani-Sommese. In addition, we determine the tensor rank and border rank of the 4 * 4 determinant and permanent tensors. Lastly, we discuss future work. This is based on joint work with Jong In Han, Taehyeong Kim, and Yeongrak Kim.
[Slides] [Video]
Speaker: Rafael Oliveira
Title: Sylvester-Gallai Configurations, Strong Algebras and Algebraic Complexity
Abstract: In its algebraic formulation, Sylvester-Gallai configurations are one of the simplest and elegant examples of the study of the power and limitations of cancellations in combinatorial algebraic geometry.
Thus, it is natural that questions about Sylvester-Gallai configurations have been studied by combinatorialists, algebraic geometers, as well as complexity theorists.
In this talk we survey the connections between Sylvester-Gallai (SG) configurations and algebraic complexity theory, starting from the first connection between SG configurations and the Polynomial Identity Testing (PIT) problem for depth-3 circuits devised by Dvir and Shpilka in 2007, the first polynomial-time algorithm using this approach due to Kayal and Saraf in 2009 and culminating into the intrinsic connection between depth-3 identities and Sylvester-Gallai configurations done by Saxena and Seshadri in 2013.
We also mention connections between robust versions of linear SG configurations and coding theory by Barak, Dvir, Wigderson, and Yehudayoff in 2011, and the reconstruction problem for depth-3 circuits done by Sinha, Saraf, Shringi, and Varadajan.
Once we have established the intimate connection between SG configurations and PIT for depth-3 circuits (the linear case), we survey Gupta's non-linear generalizations of Sylvester-Gallai configurations and their relations to the PIT problem for special classes of depth-4 circuits.
We will then survey recent progress on Gupta's SG conjectures and on deterministic polynomial-time PIT algorithms for depth-4 circuits, both done via the construction of strong algebras and other results from commutative algebra and algebraic geometry.
This talk is based on recent works with Abhibhav Garg, Shir Peleg, Akash Kumar Sengupta, Nir Shalmon and Amir Shpilka.
[Slides] [Video]
Speaker: C Ramya
Title: Efficient PIT over Nonassociative Algebras
Abstract: The difficulty in derandomizing PIT as well as obtaining strong lower bounds for arithmetic circuits is largely due to the lack of understanding of how monomials get cancelled in a circuit. In the usual polynomial ring, multiplication is both commutative and associative, and by restricting relations satisfied by the multiplication rule, we hope to understand cancellations of monomials. For example, the noncommutative polynomial ring is obtained by dropping commutativity while preserving associativity and progress on lower bounds and PIT for general noncommutative circuits has remained elusive.
We get the nonassociative polynomial algebra (commutative and non-commutative) when multiplication among formal variables is not associative. Hrubeš, Yehudayoff, and Wigderson (2010) proved exponential-size lower bounds for circuits computing explicit non-associative polynomials. In this talk, we will complement the lower bound results with PIT algorithms. We will discuss randomized polynomial-time blackbox PIT for nonassociative circuits, both in the commutative and noncommutative settings and also touch upon deterministic algorithms in depth-restricted settings.
This is based on joint work with Partha Mukhopadhyay and Pratik Shastri.
[Slides] [Video]
Speaker: Zeyu Guo
Title: Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets
Abstract: We give new explicit constructions of several fundamental objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, weak subspace designs, and strong s-blocking sets over finite fields.
Our focus is on the small-field regime, where the field size depends only on a secondary parameter (such as the rank or codimension) and is independent of the ambient dimension. This regime is central to several applications, yet remains poorly understood from the perspective of explicit constructions.
In this setting, we obtain the first explicit constructions of lossless rank extractors and weak subspace designs for r much less than k, where r denotes the rank (or codimension), over finite fields F_q with q >= poly(r) and q non-prime, with near-optimal parameters. For other finite fields, including prime fields and small fields, we obtain weaker but still improved bounds.
As a consequence, we construct explicit strong s-blocking sets in PG(k-1,q) of size O(s(k-s)q^s) for all sufficiently large non-prime fields q >= poly(s), matching the best known non-explicit bounds up to constant factors. This significantly improves the previous best bound 2^O(s^2 log s) q^s k of Bishnoi and Tomon (Combinatorica, 2026), which requires q >= 2^Omega(s).
Our approach is primarily algebraic, combining techniques from function fields and polynomial identity testing. In addition, we develop a complementary Fourier-analytic framework based on epsilon-biased sets, which yields improved explicit constructions of strong s-blocking sets over small fields.
This is joint work with Roshan Raj, Chong Shangguan, and Zihan Zhang.
[Slides] [Video]
Speaker: Devansh Shringi
Title: Reconstruction of Depth 3 Arithmetic circuits with constant top fan-in
Abstract: We consider the problem of reconstructing (exact learning) arithmetic circuits given blackbox access to evaluations of the polynomial computed by the circuit. This problem is closely connected to central questions in algebraic complexity, including circuit lower bounds, polynomial identity testing (PIT), and tensor decomposition.
The focus of the talk will be on depth-3 circuits with bounded top fan-in and on understanding their structure. We study identities computed by such circuits and analyze the set of constant-codimension subspaces on which these polynomials vanish. These structural insights lead to a quasi-polynomial time algorithm for reconstructing depth-3 circuits with any constant top fan-in. Prior subexponential reconstruction algorithms for this model were known only when the top fan-in is 2 (Sinha ’16, ’22) or 3 (Saraf-Shringi ’25), or when the underlying field is small (Karnin-Shpilka ’09).
This talk is based on joint work with Shubhangi Saraf and Narmada Varadarajan.
[Slides] [Video]
Speaker: Anuj Dawar
Title: Symmetric Algebraic Circuits - An Introduction
Abstract: Polynomials commonly studied in the context of algebraic circuit complexity (such as the determinant and the permanent) have natural permutation symmetries. Moreover, in many (but not all) cases, circuits for computing them also exhibit permutation symmetries. In this talk, I survey recent work that has sought to develop methods, based on pebble games, for establishing lower bounds on symmetric algebraic circuits. I explore the exponential separation between the determinant and the permanent in the square symmetric model, a lower bound for the determinant when richer symmetry groups are considered, as well as the characterization of matrix-symmetric polynomials that are efficiently computed by symmetric circuits.
[Slides] [Video]
Speaker: Tim Seppelt
Title: Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
Abstract: Valiant’s conjecture from 1979 asserts that the circuit complexity classes VP and VNP are distinct, meaning that the permanent does not admit polynomial-size algebraic circuits. As it is the case in many branches of complexity theory, the unconditional separation of these complexity classes seems elusive. In stark contrast, the symmetric analogue of Valiant’s conjecture has been proven by Dawar and Wilsenach (ICALP 2020): the permanent does not admit symmetric algebraic circuits of polynomial size, while the determinant does. Symmetric algebraic circuits are both a powerful computational model and amenable to proving unconditional lower bounds. In this paper, we develop a symmetric algebraic complexity theory by introducing symmetric analogues of the complexity classes VP, VBP, and VF called symVP, symVBP, and symVF. They comprise polynomials that admit symmetric algebraic circuits, skew circuits, and formulas, respectively, of polynomial orbit size. Having defined these classes, we show unconditionally that symVF ⊊ symVBP ⊊ symVP.
To that end, we characterise the polynomials in symVF and symVBP as those that can be written as linear combinations of homomorphism polynomials for patterns of bounded treedepth and pathwidth, respectively. This extends a previous characterisation by Dawar, Pago, and Seppelt (ITCS 2026) of symVP. The separation follows via model-theoretic techniques and the theory of homomorphism indistinguishability.
Although symVBP and symVP admit strong lower bounds, we are able to show that these complexity classes are rather powerful: They contain homomorphism polynomials which are VBP- and VP-complete, respectively. Vastly generalising previous results, we give general graph-theoretic criteria for homomorphism polynomials and their linear combinations to be VBP-, VP-, or VNP-complete. These conditional lower bounds drastically enlarge the realm of natural polynomials known to be complete for VNP, VP, or VBP. Under the assumption VFPT ≠ VW[1], we precisely identify the homomorphism polynomials that lie in VP as those whose patterns have bounded treewidth and thereby resolve an open problem posed by Saurabh (2016).
Joint work with Benedikt Pago and Prateek Dwivedi (STOC 2026).
[Slides] [Video]
Speaker: Susanna de Rezende and Kilian Risse
Title: Algebraic Proof Systems
Abstract: In this talk, we will survey the landscape of algebraic proof systems viewed as systems for refuting CNF contradictions. Algebraic proof systems were originally introduced as a possible route to proving AC0[p]-Frege lower bounds. This program has led to a variety of algebraic proof systems and several lower bounds in these systems, although proving AC0[p]-Frege lower bounds remains a central open problem in proof complexity.
Much of the progress in the area has been on understanding complexity measures of the polynomials appearing in a refutation, especially degree and size. Proof techniques have been developed for several proof systems yielding strong lower bounds when size is measured by the sparsity of the polynomials. In contrast, when size is measured by the complexity of computing these polynomials using restricted algebraic circuits, essentially no nontrivial lower bounds were known until recently. In fact, even proving lower bounds against sparsity measures when allowing for affine shifts of variables required fundamentally new ideas and was viewed as a breakthrough.
We will discuss both classical results and some of the latest developments in algebraic proof complexity, and highlight several directions that appear to be underexplored. No prior knowledge of proof complexity is required.
[Slides] [Video]
Speaker: Tuomas Hakoniemi
Title: Hard CNF Instances for Ideal Proof Systems
Abstract: Ideal Proof System, introduced by Grochow and Pitassi, is an algebraic proof system that allows for succinct representation of the proofs by algebraic circuits. Several unconditional lower bounds are known for subsystems of the Ideal Proof System working with restricted circuit classes. However, these lower bounds are not for propositional formulas, but for more general polynomial constraints. As such, the results are not comparable to lower bounds for propositional proof systems.
In this talk, I will present a hard CNF instance for the Ideal Proof System over read-once oblivious algebraic branching programs. The lower bound is based on monotone feasible interpolation with respect to monotone span programs and the known exponential lower bounds for this model of computation.
This talk is based on joint work with Nutan Limaye and Iddo Tzameret.
[Slides] [Video]
Speaker: Prerona Chatterjee
Title: Quasi-polynomial Frege simulation of PIT beyond Noncommutativity
Abstract: In a landmark result, Grochow and Pitassi [GP18] established a close connection between propositional proof systems (e.g., Frege and Extended Frege) and the algebraic proof system IPS. They showed that reasoning about polynomial identities—particularly the expressive power of identity witnesses within propositional systems—is central to this connection. The strongest unconditional result in this direction, due to Li, Tzameret, and Wang [LTW18], proves that Frege and noncommutative IPS are quasi-polynomially equivalent via a Frege simulation of noncommutative identity witnesses. In this talk, we will see an extension of this line of work.
Specifically, we will see that such a quasi-polynomial equivalence holds beyond the noncommutative setting. Our result applies when the commuting graph of variables is a disjoint union of two cliques of unbounded size, a structure motivated by Cartier and Foata [CF69]. This narrows the gap between noncommutative and commutative IPS, and suggests that proving Frege lower bounds via this approach may be difficult, since equivalence persists even with substantial commutativity.
As an intermediate result, we will see that polynomial identities given by formulas over such mixed variables can be proved in Frege with only quasi-polynomial blow-up. This is the strongest known class of algebraic formulas for which Frege efficiently proves identity testing. The talk is based on joint work with Abhranil Chatterjee, Utsab Ghosal, and Partha Mukhopadhyay.
[Slides] [Video]
Speaker: Anakin Dey
Title: Debordering Closure Results in Determinantal and Pfaffian Ideals
Abstract: If f(x) is easy to compute then are factors or summands of f(x) easy to compute (Grochow, Bulletin of EATCS 131, 2020)? Andrews and Forbes (STOC 2022) studied this relative complexity question in the setting of the determinantal ideals generated by the r x r minors of n x m matrices. They showed that given such a polynomial in this ideal, one can use it as an oracle to border compute the t x t determinant. This left the natural open question: can one obtain the same result without border computation? In this work, we deborder the result of Andrews and Forbes. Our results are established using a new application of the isolation lemma, combined with a careful analysis of straightening-law expansions of polynomials in determinantal ideals.
This talk is based on joint work with Zeyu Guo.
[Slides] [Video]
Speaker: Josh Alman
Title: Faster Walsh-Hadamard Transform from Matrix Non-Rigidity
Abstract: The Walsh-Hadamard transform is a simple, recursively defined linear transformation with many applications throughout algorithm design and complexity theory. The folklore "fast Walsh-Hadamard transform" algorithm computes it using only N log N arithmetic operations, which is believed to be optimal up to constant factors. In this talk, I'll give two improved constructions:
- A new algorithm which uses (23/24) N log N + O(N) arithmetic operations, giving the first improvement on the leading constant.
- A new depth-2 linear circuit of size O(N^{1.45}), improving on size O(N^{1.5}) which one gets from the fast Walsh-Hadamard transform approach.
A key idea behind both constructions is to take advantage of the matrix non-rigidty of the Walsh-Hadamard transform. A matrix is called "rigid" if it's impossible to change a "small" number of its entries to make it have "low" rank. L. Valiant showed that if a matrix is rigid, then this implies lower bounds for computing its linear transformation. However, a recent line of work has shown that many matrices of interest, including the Walsh-Hadamard transform, are actually not rigid. Although a formal converse to Valiant's result is not known, we'll make use of non-rigidity in our new constructions.
Finally, I'll discuss recent new barriers against getting further improvements using this approach, including a new lower bound using assumptions from fine-grained complexity theory, and new rigidity lower bounds for the parameters needed to improve these constructions.
Based in part on joint work with Yunfeng Guan, Baitian Li, Jingxun Liang, Ashwin Padaki, and Kevin Rao.
[Slides] [Video]
Speaker: Ben Lee Volk
Title: Finding elements of large order
Abstract: We will discuss recent progress on deterministic algorithms that, given an integer N, find an element of large multiplicative order modulo N. Such algorithms played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (2020, 2021).
Based on a joint work with Ziv Oznovich.
[Slides] [Video]
Speaker: Roshan Raj
Title: Blackbox Principal Minor Assignment
Abstract: The problem of learning a matrix from its principal minors is called the Principal Minor Assignment Problem (PMAP). This can alternatively be seen as the problem of learning an unknown matrix A over some field F, given oracle access to the coefficients of the polynomial det(A+X) where X is a diagonal matrix with distinct variables.
In this talk, we will explore a natural black-box version of PMAP. Given black-box access to evaluations of det(A+X), the goal is to learn a matrix A. In both these problems, the matrix to be learned is not necessarily unique. Finally, we will discuss an algorithm for Black-Box PMAP and its connection to other problems.
Based on joint work with Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Chandan Saha.
[Slides] [Video]
Speaker: Prahladh Harsha
Title: Fast List-Decoding and List-Recovery of Reed-Solomon Codes and Their Variants
Abstract: Reed-Solomon (RS) codes are among the most studied and widely used error-correcting codes, and decoding them efficiently is a central algorithmic challenge. In this talk, we survey the progression of list-decoding and list-recovery algorithms for RS codes and their variants, with a focus on achieving nearly-linear running times.
We begin with the fundamentals: RS codes, unique and list-decoding problems, and classical algorithms due to Welch-Berlekamp (1986), Sudan (1997), and Guruswami-Sudan (1999). We then discuss capacity-approaching list decoding via univariate multiplicity codes and folded Reed-Solomon codes, as developed by Guruswami-Rudra (2008), Guruswami-Wang (2013), and Kopparty (2013).
The main focus of the talk is obtaining nearly-linear-time versions of these algorithms. We will discuss how Alekhnovich's lattice-based techniques and fast ODE solvers can speed up these algorithms.
Based on joint works with Rohan Goyal, Mrinal Kumar, and Ashutosh Shankar.
[Slides] [Video]
Speaker: Mrinal Kumar
Title: Multivariate polynomial factorization: closure results and algorithms
Abstract: A rich line of research culminating in works of Kaltofen in the 1980s showed that factors of multivariate polynomials with small algebraic circuits and polynomially bounded degree are themselves computable by small algebraic circuits. Furthermore, these works also gave a randomized polynomial-time algorithm to factor such circuits.
Two of the central themes in this line of research since then have been to (i) prove such closure results for more structured classes of circuits, e.g., formulas and constant depth circuits, and (ii) to design efficient deterministic algorithms for multivariate factorization.
In this talk, we will discuss some of these classical results as well as some recent progress on the understanding of these questions for constant-depth algebraic circuits.
Parts of the talk will be based on joint works with Somnath Bhattacharjee, Varun Ramanathan, Shanthanu Rai, Ramprasad Saptharishi, and Shubhangi Saraf.
[Slides] [Video]
Speaker: Shanthanu S. Rai
Title: Computing GCD of univariate polynomials in constant parallel time (over any characteristic)
Abstract: The Euclidean algorithm for computing the greatest common divisor (GCD) is arguably the oldest non-trivial algorithm in print. Originally described for integers, it also applies to univariate polynomials. While efficient, the Euclidean algorithm is inherently sequential. Can it be implemented efficiently in parallel for polynomials?
In their seminal work, Andrews and Wigderson answered this affirmatively: they showed that the GCD of two univariate polynomials can be computed in constant parallel time in the arithmetic PRAM model. Equivalently, in algebraic-complexity terms, they proved that the GCD can be computed in (piecewise) algebraic circuits of constant depth and polynomial size. However, their results hold only over fields of characteristic zero and fields of large (polynomially bounded) characteristic.
In this work, we extend their result to all sufficiently large fields, regardless of characteristic. The key ingredient is an analogue of the fundamental theorem of symmetric polynomials for constant-depth algebraic circuits, strengthening a result of Bläser and Jindal for unbounded-depth circuits. Our approach crucially uses the factor closure property of constant-depth circuits, established in our earlier work.
Based on joint work with Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf.
Speaker: Magnus Hansen
Title: On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
Abstract: In this talk, we investigate the (non-)closure properties of roABP (read-once algebraic branching program) under various algebraic operations.
The main result will be non-closure of factoring, but we will also see non-closure of powering and non-closure under symmetric compositions.
These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas, and constant-depth circuits, all of which are known to be closed under these operations.
[Slides] [Video]
Speaker: Théo Fabris
Title: Negations are powerful even in small depth
Abstract: We compare the power of monotone circuits and general circuits with small depth. In the algebraic setting, we construct an n-variate polynomial P computed by a depth-3 circuit of size n^{O(1)} such that any monotone circuit computing P has size at least 2^{\Omega(n)}. This is an asymptotically optimal separation between monotone and general algebraic circuits, improving all previously known separations, including the seminal work of Valiant (1980) and recent results by Chattopadhyay, Datta, and Mukhopadhyay (2021). We then bootstrap this result to prove strong monotone separations for polynomials of constant degree, which solves an open problem from the survey of Shpilka and Yehudayoff (2010).
In the Boolean setting, we improve known separations between the NC-hierarchy and monotone circuits, and also solve an open problem by Jukna and Seiwert (2020) regarding the relative powers of greedy and pure dynamic programming algorithms.
This is a joint work with Bruno Pasqualotto Cavalar, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff. The paper is available at https://eccc.weizmann.ac.il/report/2025/219/.
[Slides] [Video]
Speaker: Pravesh Kothari
Title: Two Worlds of Algorithms for Tensor Decomposition
Abstract: Tensor Decomposition is the task of taking input an n x n x n tensor T and finding the smallest number (called the rank of T) of a_i, b_i, and c_i's such that T = \sum_i a_i \otimes b_i \otimes c_i. A classical result of Hastad shows that tensor rank decomposition is NP-hard, unlike matrix rank decomposition. Efficient algorithms, it turns out, can still go surprisingly far. And have a host of applications, famously in statistical estimation. These algorithmic results can be classified into two kinds based on the nature of the assumptions they make about T.
One line of work assumes that T is a sum of rank-1 tensors, each of which consists of vectors with independent random components. In this setting, there are efficient algorithms that succeed so long as T has rank << n^{1.5}. The algorithms are based on a clever use of semidefinite programming.
The other line of work relies on algebraic methods and succeeds when the components of T are vectors with generic components. That is, the algorithms succeed whenever the tuple of vectors that form the components comes from a Zariski-dense open set. A classical algorithm of Jennrich succeeds whenever the rank of the input tensor is <= n in this setting. The overcomplete setting (i.e., when the rank > n) has been a major challenge, and as of 2025, the best-known algorithms can handle tensors of rank (2-\eps)n.
In this talk, I will give you a brief overview of the frontier in both these directions and end with a tantalizing open question about a "hybrid" of the two kinds of models.
Based partially on joint work with Ankur Moitra and Alex Wein.
Speaker: Julian Dörfler
Title: Which Graph Motif Parameters Count?
Abstract: For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interpretation.
In this talk we will look at which graph motif parameters, i.e. linear combinations of #IndSub(H_i,*), "count something". Formally, we show which graph motif parameters are impossible to evaluate in an oracle variant of #P, where an implicit graph is accessed by oracle queries.
This is based on joint work with Markus Bläser, Radu Curticapean, and Christian Ikenmeyer.
[Slides] [Video]
Speaker: Pietro Posta
Title: Representation-Theoretic multiplicities and the class #BQP
Abstract: Representation-Theoretic multiplicities, such as Littlewood-Richardson, Kronecker, and plethysm coefficients, are a special case of branching coefficients, counting how many copies of an irreducible representation for a group H appear in an irreducible representation of a different group G. For many of these coefficients, whether you can provide a positive combinatorial interpretation is an important and well-studied open problem within the field of algebraic combinatorics. In this talk, I will explain how this is related to computational complexity and why the quantum complexity equivalent of this problem is much easier to treat.
[Slides] [Video]
Speaker: Tuukka Korhonen
Title: Lower bounds for tropical circuits and the power of pure dynamic programming
Abstract: Tropical circuits are circuits over either the (max, +) or the (min, +) semiring. They can be argued to represent "pure" dynamic programming algorithms for optimization problems. Exponential lower bounds have been known for tropical circuits since the 1980s, and they can be proven by similar techniques as for monotone algebraic circuits. I'll talk about tropical circuit lower bounds from the perspective of an algorithm designer who wishes to understand whether our current pure dynamic programming algorithms are optimal.
[Slides] [Video]