Laboratoire
Équipes
Membres
Événements
Info scientifique
Info. pratiques
Intranet LIGM
Retour à l'accueil
Séminaire Algo - Hervé Fournier
Séminaire Algo - Hervé Fournier Age: 358 days ![]() Hervé Fournier Monotone lower bounds for algebraic computations via nonnegative rank measures Salle de séminaire (4B125) - Bâtiment Copernic Abstract: Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove a rather tight lower bound for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting. Joint work with Guillaume Malod, Maud Szusterman and Sébastien Tavenas. |