Lunds Tekniska Högskola


MIAO video seminar: Superpolynomial lower bounds against low-depth algebraic circuits


Tid: 2021-11-12 14:00 till 16:00
Plats: Online - link by registration
Kontakt: jakob [dot] nordstrom [at] cs [dot] lth [dot] se
Spara händelsen till din kalender

Title: Superpolynomial lower bounds against low-depth algebraic circuits

Speaker: Nutan Limaye, IT University of Copenhagen

Host: Jacob Nordström, Department of Computer Science, Lund University Joint with

Where: Online - link by registration


Every multivariate polynomial P(X) can be written as a sum of monomials, i.e. a sum of products of variables and field constants. In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P.

What happens if we add another layer of complexity, and consider sums of products of sums (of variables and field constants) expressions? Now, it becomes unclear how to prove that a given polynomial P(X) does not have small expressions. In this result, we solve exactly this problem.

More precisely, we prove that certain explicit polynomials have no polynomial-sized "Sigma-Pi-Sigma" (sums of products of sums) representations. We can also show similar results for Sigma-Pi-Sigma-Pi, Sigma-Pi-Sigma-Pi-Sigma and so on for all "constant-depth" expressions.

In the first part of this two-part talk, I will present the statements of the main results and some background. In the second part of the talk, I will give some proof details.

This is a joint work with Srikanth Srinivasan and Sébastien Tavenas.

Please register at in order to get an access link to the zoom platform.

The MIAO video seminars are arranged by the  Mathematical Insights into Algorithms for Optimization (MIAO) research group at the University of Copenhagen and Lund University. Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break an optional ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results. For listeners who are particularly interested, there is then an opportunity to return for a second part where we get into more technical details.