Résumé | In this talk, I will introduce a few computational models, known as (algebraic) circuits and formulas, and as branching programs (ABPs). Restricted classes of computation, such as monotone circuits, or non-commutative ABPs, have been investigated through the past decades. In the latter setting, a family of matrices (Nisan matrices) naturally appears, their ranks are related to the optimal size of a circuit computing the target polynomial. Recently, we investigated weak monotonicity (a relaxation of the monotonicity constraint), and found some explicit polynomials for which the weak-non-negative ranks don’t characterize the minimal size of an ABP computing them. The sum of ranks still gives a lower bound on minimal-size computation, and this can be used, for instance, to obtain a quadratic lower bound when computing the elementary symmetric polynomial. Joint work with Hervé Fournier, Guillaume Malod, and Sébastien Tavenas. |