Evènement pour le groupe Séminaire Méthodes Formelles


Date 2020-11-24  14:00-15:00
TitreMonotone ABPs complexity vs. monotone rank of some explicit polynomials 
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.  
LieuOnline 
OrateurMaud Szusterman 
Emailmaud.szusterman@imj-prg.fr 
UrlIMJ-PRG 



Aucun document lié à cet événement.

Retour
Retour à l'index