| Resumé |
La thèse est en trois parties, relativement indépendantes. La première partie correspond à un travail en commun avec H. Fournier, G. Malod, et S. Tavenas. On cherche à caractériser la complexité monotone (minimale) de branching programs (algébriques) calculant des polynômes non-commutatifs. Nisan (1991) avait conjecturé que le rang positif caractérise la complexité minimale : nous exposons un contre-exemple à cette conjecture dans le cadre monotone. On établit une borne inférieure pour la complexité (monotone) du calcul des polynômes symétriques élémentaires : pour ces polynômes, le cadre monotone correspond au cadre homogène syntaxiquement multilinéaire. --- La seconde partie est consacrée à la complexité d'extension (nombre minimal de facettes d'une extension affine). On étudie d'abord la complexité d'extension pour les groupes de réflexion. On revient en particulier sur les exemples du n-gone régulier et du n-permutoèdre, étudiés par Goemans (2005) et par Fiorini-Rothvoss-Tiwary (2012), et qui avaient donné deux extensions explicites assez différentes de ces polytopes : une construction séquentielle de nature combinatoire, et une construction par factorisation (positive) de la slack-matrice. En comparant les modèles, on établit que l'extension affine de Goemans est, à changement affine de coordonnées près, une section de la construction ultérieure. Ensuite on présente une modification du modèle de protocoles aléatoires proposé par Faenza-Fiorini-Grappe-Tiwary. Leur modèle, via le théorème de Yannakakis offre une caractérisation de la complexité d'extension dans le langage des protocoles de communication. En déplaçant le curseur sur le nombre de rounds de communication plutôt que le coût classique, on retrouve cette caractérisation du rang (positif) de la slacke-matrice. De plus, ce modèle alternatif donne une caractérisation originale de la complexité symétrique d'extension d'un polytope. --- La dernière partie est consacrée à un problème de géométrie convexe affine. L'inégalité de Fenchel, qui découle de Brunn-Minkowski, donne une majoration d'un produit de volumes mixtes par un autre, avec constante 2. Soprunov et Zvavitch, s'appuyant sur le théorème BKK, dérivent cette même majoration, avec constante 1, pour le n-simplexe, et conjecturent (2015) que le sup-ratio est supérieur (strict) à 1 pour tout autre corps convexe que le simplexe. Lorsqu'on se restreint aux polytopes (de dimension n), cette conjecture est démontrée (théorème de Saroglou-Soprunov-Zvavitch, 2018), mais reste ouverte au sein de la famille plus large des corps convexes, pour n'4. Cependant des conditions nécessaires sur les minimiseurs sont connues (telles que : nulle part de courbure positive sur le bord), et nous apportons de nouvelles telles conditions, qui nous permettent d'obtenir une nouvelle démonstration de la conjecture de Soprunov-Zvavitch, pour la dimension 3. . |