TCS+ Talk: Nutan Limaye on Superpolynomial Lower Bounds for Low-Depth Algebraic Circuits 🧠

Title: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Abstract: 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.

The talk is based on a joint work of Nutan Limaye, Srikanth Srinivasan,
and Sébastien Tavenas.