|
|
||
|
IMADA -Department of Mathematics and Computer Science |
|
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 this talk we will present the background behind this result and sketch the details of some of the main ideas involved in the proof. Host: Joan Boyar SDU HOME | IMADA HOME Daniel Merkle |