View abstract

Session II.3 - Real-Number Complexity

Friday, June 16, 17:00 ~ 17:30

Superpolynomial lower bounds for circuits of constant depth

Sébastien Tavenas

CNRS, Université Savoie Mont Blanc, France   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Any multivariate polynomial $P(X_1,...,X_n)$ can be written as a sum of monomials, i.e., a sum of products of variables and constants of the field. The natural size of such an expression is the number of monomials. But, what happens if we add a new level of complexity by considering expressions of the form: sum of products of sums (of variables and constants)? Now it becomes less clear how to show that a given polynomial has no small expression. In this talk we will solve exactly this problem. More precisely, we prove that some explicit polynomials do not have polynomial-sized sum-of-products-of-sums (SPS) representations. We can also obtain similar results for SPSPs, SPSPSs, etc. for all expressions of constant depth. We will see also why this problem can be seen an important step for obtaining lower bounds on the size of algebraic circuits.

Joint work with Nutan Limaye (ITU Copenhagen) and Srikanth Srinivasan (Aarhus University).

View abstract PDF