Polynômes, circuits arithmétiques, et chaînes additives

ISBN-13: 9783841795380 / Francuski / Miękka / 2018 / 96 str.

Yara Elias

Opis

Un circuit arithmétique dont les entrées sont des entiers ou une variable x et dont les portes calculent la somme ou le produit représente un polynôme univarié. On assimile la complexité de représentation dun polynôme par un circuit arithmétique au nombre de portes multiplicatives minimal requis pour cette modélisation. Et lon cherche à obtenir une borne inférieure à cette complexité en fonction du degré d du polynôme. A une chaîne additive pour d, correspond un circuit arithmétique pour le monôme de degré d. La conjecture de Strassen prétend que le nombre minimal de portes multiplicatives requis pour représenter un polynôme de degré d est au moins la longueur minimale dune chaîne additive pour d. La conjecture de Strassen généralisée correspondrait à la même proposition lorsque les portes du circuit arithmétique ont degré entrant g au lieu de 2. Le livre consiste dune part en une généralisation du concept de chaînes additives, et une étude approfondie de leur construction. On sy intéresse dautre part aux polynômes qui peuvent être représentés avec très peu de portes multiplicatives. On combine enfin les deux études en lien avec la conjecture de Strassen.

O autorze

Elias, YaraNée le 11 Octobre 1989 au Liban, Yara Elias est titulaire d'un baccalauréat en mathématiques pures et appliquées et d'une maîtrise en informatique théorique achevés à l'Université De Montréal. Actuellement, elle entreprend un doctorat en théorie des nombres à l'Université McGill.