-
Monomials in arithmetic circuits: Complete problems in the counting hierarchy
International audience -
Arithmetic circuits: the chasm at depth four gets wider
In their paper on the ''chasm at depth four'', Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size... -
Representations of polynomials, algorithms and lower bounds
Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory... -
A tau-conjecture for Newton polygons
One can associate to any bivariate polynomial P(X,Y) its Newton polygon. This is the convex hull of the points (i,j) such that the monomial X^i Y^j appears in P with a...
