Breaking Barriers: Superpolynomial Lower Bounds for Low-Depth Algebraic Circuits 📉

Computer Science/Discrete Mathematics Seminar I

Topic: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits I : An overview
Speaker: Srikanth Srinivasan
Affiliation: Aarhus University
Date: September 27, 2021


Every multivariate polynomial P(x_1,...,x_n) 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_1,...,x_n) 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 part I of this two-part talk, we will discuss the background behind this result and some basic results from this area. In part II of this talk, we will give details of the lower bound.

Based on joint work of Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas.