Nutan Limaye: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
Tuesday, October 12, 2021 - 4:00pm to 5:00pm
Location:
Email jmtaft@mit.edu for link
Seminar group:
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.