Nutan Limaye: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Tuesday, October 12, 2021 - 4:00pm to 5:00pm
Email for link
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.