Octobre 2007 Vendredi 12 octobre  Patrick Sole (INRIA, Sophia Antipolis) Codes sur GR(4,2) Résumé : Ceci est la suite de l'exposé du 25 janvier 2007 (pdf) Vendredi 19 octobre (reporté) Bruno Salvy (INRIA Rocquencourt) Équations différentielles pour les séries algébriques Résumé : Le calcul des coefficients des séries algébriques (c'est-à-dire solutions de polynômes en deux variables) est important pour l'énumération des langages context-free et pour leur génération aléatoire. Une méthode classique repose sur l'utilisation d'équations différentielles linéaires. Nous présentons cette méthode et ses avantages du point de vue de la complexité. Nous montrons ensuite qu'il est possible d'améliorer l'efficacité de cette méthode en recherchant une équation différentielle d'ordre élevé, mais avec des coefficients de degré modéré. Nous en déduisons un algorithme plus efficace que ses prédécesseurs, s'étant affranchi du poids de trop nombreuses singularités apparentes. Il s'agit d'un travail en commun avec Alin Bostan, Frédéric Chyzak, Grégoire Lecerf et Éric Schost. Janvier 2008 Vendredi 18 janvier Philippe Gaborit (Université Limoges) Utilisation des codes quasi-cycliques pour les cryptosystèmes basés sur les codes correcteurs d'erreurs. Résumé: Un des problemes principaux pour le developpement des systemes a cle publique basés sur les codes correcteurs d'erreurs est la trop grosse taille des clés publiques. Dans cet exposé nous présentons une méthode pour diminuer la taille des cryptosystèmes basés sur les codes correcteurs comme les schémas de MEliece et de Niederreiter. L'idée principale est d'utiliser des descriptions plus compactes de matrices a base de codes quasi-cycliques. On montrera comment ce point de vue permet de reduire la taille des clés dans certains systemes de chiffrement basés sur les codes jusqu'a quelques dizaines de kilobits plutot que des centaines de kilobits ou encore à quelques centaines de bits pour des schemas d'authentification. On montrera aussi dans ce cadre comment les codes quasi-cycliques font mieux que les codes aleatoires et permettent d'obtenir des codes meilleurs asymptotiquement que la borne de Gilbert-Varshamov et qui peuvent etre utilisés pour de tels systemes. Vendredi 25 janvier Dimitri Grigoryev (IRMAR) Complexité de communication probabiliste sur le corps réel. Résumé: La complexité de communication compte le nombre d'échanges des informations entre deux (ou plus) parties en ignorant leurs calculs propres. La complexité de communication dans le modèle de calculs discrets est bien étudiée. On introduit des protocoles de communication dans le modèle de calculs avec polynômes réels et obtient des bornes inférieures sur la complexité de communication (déterministe et probabiliste), en particulier pour le problème du sac-à-dos. Février 2008 Vendredi 22 février 2008 Frédéric Chyzak (INRIA Rocquencourt) Multiples communs d'opérateurs linéaires différentiels et à différences. Résumé. Le calcul du plus petit commun multiple de plus de deux opérateurs linéaires, différentiels ou à différences, intervient dans des problèmes comme l'extraction de sous-séries de séries multi-sommables, en théorie de la resommation, ou pour la sommation symbolique de fonctions rationnelles. Hormis dans ces quelques cas où les opérateurs dont on considère le p.p.c.m. sont très structurés, le p.p.c.m. d'opérateurs linéaires généraux ne semble avoir été étudié que dans le cas restreint de deux opérateurs, par une généralisation de la méthode des sous-résultants. Par ailleurs, van der Hoeven a montré en 2000 comment le produit d'opérateurs différentiels linéaires généraux (en caractéristique nulle) se ramène au produit de matrices. Tout récemment, Bostan, Chyzak et Le Roux ont même montré l'équivalence des deux problèmes en complexité (toujours en caractéristique nulle). Il devient ainsi tout naturel, à l'imitation du cas commutatif, de prendre pour étalon le coût du produit de matrices et d'essayer d'y ramener d'autres problèmes de l'algorithmique des opérateurs linéaires. Dans cette double perspective, nous nous intéressons ici aux calculs en bonne complexité de multiples communs d'opérateurs à coefficients polynomiaux généraux. Il apparaît tout d'abord que le calcul de p.p.c.m. itérés est une mauvaise approche. Nous développons ensuite une première reformulation linéaire du problème donnant une borne précise sur le degré des coefficients du p.p.c.m. en fonction des degrés des entrées. Cette borne permet l'analyse de plusieurs algorithmes, existants ou nouveaux, pour le calcul du p.p.c.m. Une meilleure complexité est obtenue en relâchant la contrainte de minimalité du p.p.c.m. : une nouvelle reformulation linéaire montre qu'il existe des multiples communs de taille bien moindre que celle du p.p.c.m. En en calculant deux en bonne complexité, puis en en prenant un p.g.c.d., on obtient un bon algorithme pour le calcul du p.p.c.m. (Travail en cours avec A. Bostan, Z. Li et B. Salvy.) Mars 2008 Vendredi 7 mars 2008 Guillaume Moroz (LIP6) Décomposition régulière d'un idéal polynomial. Vendredi 14 mars 2008 Lionel Chaussade (IRMAR) Codes tordus dont le rang ou la distance minimale est prescrite. Résumé Nous étudierons le lien entre les équations aux différences sur un corps fini et les polynômes tordus. Cette analogie donnera une méthode pour engendrer des theta-codes dont on pourra contrôler le corps de définition et la distance rang. Une approche différente nous permettra de générer des codes BCH tordus dont la distance minimale sera prescrite. Avril 2008 Vendredi 4 avril 2008 Alain Couvreur (Université de Toulouse) Construction de codes différentiels sur des surfaces algébriques Résumé: La première partie de cet exposé consistera en une présentation de la théorie des codes correcteurs construits à partir de courbes algébriques. On distingue dans cette théorie deux types de constructions respectivement appelées fonctionnelle et différentielle. Les relations d'orthogonalité entre ces deux types de codes sont à la base de nombreux algorithmes de décodage. Dans une seconde partie nous nous intéresserons aux codes construits à partir de surfaces. Cette théorie, moins développée que la précédente, ne porte à l'heure actuelle que sur des codes de type fonctionnels. Nous proposerons une généralisation de la construction différentielle puis étudierons les propriétés de ces nouveaux codes ainsi que leurs relations avec les codes fonctionnels. Nous terminerons sur les perspectives de décodage qu'ouvre une telle construction. Vendredi 11 avril 2008 Markus Schweighofer (IRMAR) Problème des moments tronqué et bases de Gröbner Résumé: Curto et Fialkow ont démontré en 1996 un critère suffisant pour qu'une famille de nombres réels soit la famille des moments d'une mesure jusqu'à un certain ordre. Cette contribution au problème des moments tronqué est aujourd'hui importante pour l'optimisation globale des polynômes. La partie ardue de la preuve consiste à prolonger la famille des moments au fur et à mesure tout en préservant la validité du critère. Nous avons récemment observé que cette étape de la preuve auparavant très calculatoire peut être effectuée et mieux comprise avec les bases de Gröbner. Vendredi 18 avril 2008, deux exposés Colas Bardavid (IRMAR) à 10h15 Réalisation différentielle d'extensions galoisiennes. M'hamed El Kahoui (Université Cadi Ayyad, Marrakech) à 11h30 Topologie des courbes en dimension trois. Mai 2008 Vendredi 2 mai 2008 Delphine Boucher (IRMAR) Codes sur les anneaux de polynômes tordus Résumé : Les codes cycliques sur un corps fini sont obtenus à partir des idéaux d'un anneau quotient de l'anneau des polynômes. Dans cet exposé, on montre comment on peut généraliser cette approche en utilisant des anneaux de polynômes tordus (anneaux de Ore). Ces codes correspondent à des idéaux à gauche d'anneaux quotients de l'anneau des polynômes tordus. On abordera quelques-unes de leurs propriétés : dualité , constructions de codes auto-duaux en utilisant les bases de Groebner; décodage, première adaptation des codes type BCH; généralisation des codes tordus en utilisant des anneaux de Galois au lieu de corps finis pour les coefficients des polynômes. Ce travail a été réalisé avec W. Geiselmann et F. Ulmer ainsi qu'avec P. Solé et F. Ulmer (pour les anneaux de Galois). Il a fait l'objet d'études récentes (L. Chaussade, P. Loidreau et F. Ulmer sur les codes tordus de distances ou rangs prescrits). Vendredi 16 mai Thierry Berger (Xlim, Université de Limoges) Quelques résultats autour de la métrique rang et des codes de Gabidulin. Vendredi 30 mai Guy Casale (IRMAR) Une preuve du théorème de Morales-Ramis-Simo à l'aide de la théorie de Malgrange. Juin 2008 Vendredi 13 juin Nicolas Le Roux (INRIA Rocquencourt) Produit d'opérateurs linéaires différentiels par évaluation et interpolation. Résumé : Joris van der Hoeven a montré en 2002 que le produit d'opérateurs différentiels (en caractéristique nulle) peut se ramener à un nombre constant de  produits de matrices  par un algorithme d'évaluation-interpolation. Il a de plus posé la question suivante : Peut-on réduire un produit de matrices  à un nombre constant d'opérateurs différentiels? Dans cet exposé, je répondrai positivement à la question sous réserve que les ordres et degrés sont de taille comparable. J'expliquerai ensuite comment réduire le nombre de produits de matrices, grâce à un nouvel algorithme d'évaluation-interpolation plus direct. Je discuterai enfin de l'optimalité d'une telle approche par évaluation-interpolation dans d'autres situations : -  cas où les ordres et degrés sont de taille déséquilibrée ; -  cas où les opérateurs sont creux. -  en petite caractéristique ; (Travail en collaboration avec Alin Bostan et Frédéric Chyzak)