Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits : An overview
1 : LAMA
LAMA, Centre national de la recherche scientifique - CNRS (France)
Every multivariate polynomial P(x1, ..., xn) 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. 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(x1, ..., xn) does not have small expressions. We will discuss the background behind this question, the relations with standard Boolean complexity and some basic results from this area. Finally we will present the last results on these questions.
- Poster