Séminaire de calcul formel et complexité (2012-2013)

Le séminaire a lieu environ deux fois par mois, les vendredis, de 10:30 à 12:00, salle 016, rez-de chaussée du bâtiment 22, Campus de Beaulieu

 

Prochaines séances 
 

Vendredi 31 mai 2013
Gwezheneg Robert (IRMAR)
Métrique rang et codes de Gabidulin en caractéristique zéro.

Résumé : Après avoir introduit les $theta$-polynômes et précisé plusieurs de leurs propriétés (notamment le lien entre leur degré et la dimension de l'espace des racines, ainsi que la construction d'un $theta$-polynôme s'annulant sur un espace donné), je donnerai 4 définitions de métrique "rang". Nous verrons qu'il n'y a en fait que deux métriques distinctes, et que celles-ci sont en fait identiques sous une hypothèse raisonnable. Enfin, nous verrons comment généraliser les codes de Gabidulin (codes correcteurs sur des corps finis et en métrique rang) à des corps de caractéristique nulle, ainsi qu'un algorithme de décodage qui reste valable.
Vendredi 13 septembre 2013
Xavier Caruso (IRMAR)
Algorithmes pour les polynômes tordus sur un corps fini


Séances passées

 

Vendredi 28 septembre
Jacques-Arthur Weil (XLIM, Limoges)
Intégrabilité de systèmes hamiltoniens : une version effective du critère de Morales-Ramis-Simo
(travail commun avec Ainhoa Aparicio)

Résumé. Le critère de Morales-Ramis-Simo permet de tester l'intégrabilité ou non de systèmes dynamiques hamiltoniens en étudiant les équations variationelles obtenues en étudiant le comportement de trajectoires proches d'une trajectoire connue. Techniquement, il s'agit de tester si ces équations (de grands systèmes différentiels linéaires) ont un groupe de Galois différentiel virtuellement abélien.
Nous montrerons comment cette condition, d'apparence bien abstraite, peut-être testée effectivement en utilisant une technique de réduction de systèmes différentiels linéaires à une forme sur laquelle l'algèbre de Lie du groupe de Galois se lit bien.
L'exposé se voudra auto-contenu ;  nous utiliserons essentiellement des idées simples sur les algèbres de Lie et de l'algèbre linéaire classique.

 

Vendredi 5 octobre
Alexandre Le Meur
Certificats de positivité pour plusieurs polynômes en une seule variable

 

Vendredi 19 octobre
Daouda Niang Datta
Caractérisation de type Hurwitz des Systèmes Commutés Planaires Globalement Uniformément Asymptotiquement Stables

Abstract:
My talk will focus on recent results concerning the stability problem for the planar linear switched system x'(t) = u(t) A x(t) + (1 − u(t)) Bx(t) , x = (x1, x2) in R2 where the real matrices A, B are Hurwitz and for t>0 u(t) in {0,1} is a measurable function.
We give a Hurwitz like characterization of globally uniformly asymptotically stable planar switched systems. We will also give a "practical" version of the main result in [NS] using real algebraic geometry tools.
This new approach give a Hurwitz like characterization of switched systems which share a same strict or large common quadratic Lyapunov function and simplify the main result in [BBM].

References :
- [BBM] M. Balde, U. Boscain, P. Mason, A note on stability conditions fo planar switched systems , international journal of control, Vol 82, n 10, 1882-1888, (2009).
- [NS] R. Shorten and K. Narendra. Necessary and sufficient conditions for the existence of a common quadratic Lyapunov function for two stable second order linear time-invariant systems. In Proceedings 1999, American Control Conf., pages 1410-1414, 1999.
- [BBMZ ]M. Benaïm, S. L. Borgne, F. Malrieu and P. A. Zitt "On the stability of planar randomly switched systems"

 

 

 Vendredi 9 novembre
Tristan Vaccon (IRMAR)
Algorithme F5 matriciel et évaluation de sa perte de précision. Application vers un calcul de base de Gröbner p-adique.

Résumé :
Jean-Charles Faugère a proposé en 2002 un nouvel algorithme de calcul de bases de Gröbner dont le principe, étudié ensuite par Magali Bardet en 2004, est entièrement matriciel : l'algorithme F5 matriciel. Il se trouve à ce jour parmi les algorithmes les plus rapides pour le calcul d'une base de Gröbner.
Après une présentation de cet algorithme, nous verrons qu'il peut être adapté pour étudier le calcul d'une base de Gröbner de polynômes connus de manière approchée, et en particulier, contrôler les pertes de précision dans ce calcul.
On s'intéressera plus particulièrement au cas du calcul d'une base de Gröbner sur Q_p.

Références :
Jean-Charles Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, ISSAC '02, pages 75-83, New York, NY, USA, 2002. ACM.
M. Bardet, "Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie", thèse de doctorat, Université Paris VI, Décembre 2004.

 

 

Mardi 20 novembre à 14h00 en salle des thèses, bâtiment 2A, Campus de Beaulieu.
Soutenance de thèse de Matthieu Legeay
Titre : "Utilisation du groupe de permutations d'un code correcteur pour améliorer l'efficacité du décodage"

 

 

Vendredi 23 novembre, exceptionnellement deux exposés, à 10h30 et à 11h30

--10h30 : Clément Pernet (Université Joseph Fourier, Grenoble, LIG)
Adaptive decoding for dense and sparse evaluation/interpolation codes

Abstract: We will present recent work on evaluation-interpolation error correcting codes. It is motivated in
the study of algorithm based fault tolerance (ABFT) applied to parallel exact linear algebra.
Indeed evaluation/interpolation schemes allow to split the computational load of one problem into
several independent tasks, making the problem embarassingly parrallel.
In the context where soft-errors occur during the computation of some of these tasks, the
evaluation/interpolation codes make it possible to still recover the result provided that some
amount of redundant information has been computed.

In a first part we will focus on the interpolation of dense polynomials with errors, and their
equivalent over the ring of integer: the CRT-codes (Chinese Remainder Theorem).
We will introduce a more general error model allowing to derive tighter bounds on the error
correction capacities of such codes. Then we will describe some improvements making the error
correction capacity adaptive with respect to the exact amount of information of the result to be
computed.

In a second part we will focus on the interpolation of sparse polynomials with errors. After proving
a lower bound on the required number of evaluation points, we will present a unique decoding algorithm matching that bound and a list-decoding variant of it, with a lesser requirement on the number of evaluations.

--11h30 : Ilya Dumer (University of California at Riverside)
Covering a sphere with  spheres: Rogers bound revisited.

Abstract : Given a sphere of any radius in an n-dimensional Euclidean space, we study the coverings of this sphere with unit spheres of radius 1. Our goal is to design a covering of the lowest covering density, which defines the average number of unit spheres covering a point in a bigger sphere. For growing n, we obtain the covering density of the order (n ln n)/2 or less.   The techniques combine random-coding arguments with new "porous" covering design and  geometric estimates. This new bound gives the lowest covering density known to date and is half the order n ln n established in the classical Rogers bound of 1956.

 

 

Vendredi 7 décembre
Christophe Tran (IRMAR)
Calcul de couplages sur courbes elliptiques via les Elliptic Net, relations avec les fonctions thêta.

 Résumé :
Dans les années 2000, l'utilisation des couplages en cryptographie a permis le développement de nombreux protocoles . Jusqu'à récemment, le calcul des couplages reposait exclusivement sur l'algorithme de Miller. En 2007, Katherine Strange proposa une méthode originale de calcul du couplage de Tate,  basée sur l'utilisation d'un outil provenant de la théorie des suites récurrentes, les elliptic nets. Après avoir étudié cet algorithme, nous examinerons les liens profonds entre la théorie des elliptic net et celle des fonctions thêta. En particulier, on verra que la formule du couplage de K. Strange est un cas particulier de la formule donnée par David Lubicz et Damien Robert.

 

 

Vendredi 18 janvier
Pierre-Jean Spaenlehauer (University of Western Ontario/INRIA)
Résolution de systèmes polynomiaux structurés et applications en Cryptologie et en Géométrie Réelle.

Résumé. Les systèmes polynomiaux multi-homogènes, déterminantiels et booléens jouent un rôle prépondérant dans plusieurs applications en Cryptologie, en Géométrie Réelle et en Optimisation. Dans cet exposé, par des méthodes de calcul de bases de Gröbner et sous des hypothèses de généricité sur les coefficients de ces systèmes, je présente de nouvelles bornes de complexité asymptotique pour leur résolution :
 - dans le cas déterminantiel et dans le cas bilinéaire, ces bornes permettent d'identifier des sous-familles de systèmes pour lesquelles la complexité de résolution est polynomiale en le nombre de solutions ;
 - pour les systèmes quadratiques booléens, un nouvel algorithme de résolution est proposé. Pour un système de n équations en n variables, l'espérance de la complexité d'une variante probabiliste est O(2^(0.792 n)) sous des hypothèses algébriques sur le système d'entrée, ce qui permet de résoudre exponentiellement plus rapidement que par recherche exhaustive.

L'obtention de ces bornes passe par une analyse de la structure algébrique de ces systèmes ; ceci conduit à des formules explicites pour la série de Hilbert générique des idéaux associés. Cette analyse sera illustrée par des applications en Cryptologie (cryptanalyse de MinRank, HFE et QUAD) et en Géométrie Réelle (calcul de points critiques).

Travaux commun avec Jean-Charles Faugère et Mohab Safey El Din (systèmes déterminantiels et multi-homogènes) et avec Magali Bardet, Jean-Charles Faugère et Bruno Salvy (systèmes booléens).

  

 

Vendredi 25 janvier
Romain Basson (IRMAR)Algèbre d'invariants des formes binaires en caractéristique positive

Résumé. Le développement d'une algorithmique pour les espaces de modules de courbes hyperelliptiques (en petit genre) peut s'envisager via la théorie classique des invariants des formes binaires ; une courbe hyperelliptique de genre g étant simplement reliée à une forme binaire de degré 2g+2. La description et la construction effective de ces algèbres d'invariants en caractéristique nulle ont débuté dans la seconde moitié du XIXème siècle, donnant d'ailleurs naissance aux prémices de l'algèbre commutative, et culminé en 1967 avec le résultat de Shioda concernant les octiques (qualifié de "tour de force" par Mumford !). En revanche, le cas des petites caractéristiques positives reste largement ouvert, notamment pour les octiques. Ainsi, après avoir donné un aperçu de la théorie classique, j'exposerai les résultats actuels concernant les algèbres de formes octiques en petites caractéristiques positives.

 

Vendredi 8 février, exceptionnellement à 11h30

Alexei Tsygvintsev (UMPA, ENS Lyon)

Equations différentielles en biologie :  du Lotka-Volterra à Kirschnter et Panetta


Résumé :
En 1986 Kirschner et Panetta ont proposé un modèle mathématique  pour décrire comment le  système immunitaire contrôle le développement de cancer.
Nous discutons les applications et prévisions basées sur ce modèle et montrons comment le  phénomène de réapparition instantanée du cancer, qui échappe au système immunitaire,  peut être analysé.
En modélisation nous utilisons le système de 3 équations différentielles avec paramètres. Pour analyser les diverses questions de stabilité, d'existence des variétés invariantes etc il est nécessaire d'appliquer le calcul formel vu la complexité du problème.


Références
1. A. Tsygvintsev, D. Kirschner, S. Marino, A mathematical model of Gene Therapy for the Treatment of Cancer , in the book  "Mathematical Models and Methods in Biomedicine", Springer Verlag, berlin,  2012
2. D. Kirschner, A. Tsygvintsev. On the global dynamics of a model for tumor immunotherapy, Journal of Mathematical Biosciences and Engineering, Volume 6(3), pp 573-583, 2009

 

Vendredi 15 mars
Antonia Wachter-Zeh (Ulm University & IRMAR)
Bounds on list decoding rank metric codes.

Abstract : Gabidulin codes can be seen as the analogs of Reed–Solomon (RS) codes in rank metric. There are several efficient decoding algorithms up to half the minimum rank distance. However, in contrast to RS codes, there is no polynomial-time list decoding algorithm; it is not even known, whether such an algorithm can exist or not. An exponential lower bound on the number of codewords in a ball of radius τ around the received word would prohibit polynomial-time list decoding since the list size can be exponential, whereas a polynomial upper bound would show that it might be possible. 
We provide bounds on the list size of rank metric codes in order to understand whether polynomial-time list decoding is possible or not. Three bounds on the list size are proven. 
The first is a lower exponential bound for Gabidulin codes and shows that for Gabidulin codes no polynomial-time list decoding beyond the Johnson radius exists. 
Second, an exponential upper bound is derived, which holds for any rank metric code of length n and minimum rank distance d. 
The third bound proves that there exists a rank metric code such that the list size is exponential in the length for any radius greater than half the minimum distance. 
This implies that there cannot exist a polynomial upper bound depending only on n and d as the Johnson bound for Hamming metric. All three bounds reveal significant differences to codes in Hamming metric.
Vendredi 22 mars
Alexander Zeh (Ulm University & LIX)
Minorer la distance minimale d'un code cyclique par intégration dans un code produit.

Abstract
A cyclic code is associated with another cyclic code to bound its minimum distance by considering the corresponding (cyclic) product code. The algebraic relation between these two codes allows the formulation of syndromes and a key equation.
We outline the decoding approach for the case of errors and erasures and show how the Extended Euclidean Algorithm can be used for decoding.
Vendredi 29 mars
Thierry Combot (IMCCE)
Algorithmes pour la non-intégrabilité

Résumé Soit V une fonction rationnelle en deux variables, homogène de degré k et avec des paramètres a. Nous présentons un algorithme construisant une liste de conditions polynomiales sur a nécessaires pour l'intégrabilité du système dynamique associé au potentiel V. Lorsque ces conditions sont satisfaites, le potentiel V satisfait au moins toutes les contraintes d'intégrabilité de Morales-Ramis-Simo à l'ordre 2 au voisinage de toutes les orbites homothétiques, sauf éventuellement dans un cas particulier avec k pair. On applique cet algorithme sur des exemples déjà traités, permettant de reproduire et de corriger certains résultats, et d'aller plus loin dans le cas V polynomial.
Travail en collaboration avec Alin Bostan et Mohab Safey-El-Din.
 
 
 
 
Archives 2011-2012

 

Mercredi 21 septembre 2011, salle 006
Antonia Wachter (Ulm University & IRMAR)
A class of convolutional codes based on Gabidulin codes

Abstract:
(Partial) Unit Memory ((P)UM) codes provide a powerful possibility to construct convolutional codes based on block codes in order to achieve a high decoding performance. There exist several constructions based on Reed-Solomon or BCH codes.
Here, a construction based on Gabidulin codes is considered. This construction requires a modified rank metric, the so-called sum rank metric.
For the sum rank metric, the free rank distance, the extended row rank distance and its slope are defined analogous to the extended row distance in Hamming metric, which essentially determines the error-correcting capability of a convolutional code.
We derive upper bounds on the free rank distance and the slope of (P)UM codes in the sum rank metric and give an explicit construction of (P)UM codes based on Gabidulin codes, achieving the upper bound on the free rank distance.
Using the algebraic structure of the underlying block code, efficient decoding of this convolutional code is possible.
For this purpose, we generalize Dettmar and Sorger's Bounded Minimum Distance (BMD) decoding algorithm for (Partial) Unit Memory ((P)UM) codes
to PUM constructions of arbitrary rate and to error-erasure correction and adapt it to rank metric.
The correctness of the generalized decoding algorithm is proven and it is shown that the complexity of decoding one block is cubic in its length.

 

Vendredi 28 ocotbre 2011
David Lubicz (DGA-MI & IRMAR)
Algèbre linéaire sur W(\F_p)[[u]]
Application au calcul de certaines représentations Galoisiennes
(travail en commun avec Xavier Caruso)

Résumé :
A la base des théories de Fontaines, Breuil et Kisin, il y a  des (anti-)équivalences de catégories qui permettent de manipuler certaines représentations Galoisiennes en faisant des calculs sur des modules muni de certaines structures (Frobenius, filtration etc.).
Comme application de ce principe, nous montrons comment calculer certains invariants associés à certaines Q_p représentations en rendant effectif un résultat récent de Génestier et Lafforgue.

 

Vendredi 18 novembre 2011

JNCF 11 au CIRM du 14 au 18 novembre

 

24 et 25 Novembre 2011
Workshop GEOLMI

 

Vendredi 3 février 2012
Cyril Cohen (LIX)
Formalisation de  l'élimination des quantificateurs pour les corps réels clos en COQ.

Résumé.
Cet exposé décrit la formalisation d'une procédure d'élimination des quantificateurs pour les corps réels clos et de sa preuve de correction dans l'assistant de preuve Coq. Celui-ci permet à la fois de programmer l'algorithme, de le spécifier et de prouver formellement sa correction dans un même environnement. Nous nous intéresserons particulièrement aux divergences entre les formulations sur papier et sur machine. Il peut s'agir de détails à fournir que l'on avait omis pour le lecteur humain et qui peuvent être plus ou moins essentiels pour la machine. Ou bien il peut s'agir de reformulations que la programmation nous permet de faire pour nous épargner du travail. De plus, nous nous attacherons à bien distinguer les parties "algorithmiques" des parties "mathématiques" du développement, car, bien que décrites dans le même langage, elle jouent un rôle fondamentalement différent.

Vendredi 10 février 2012
Morgan Barbier (GREYC, Caen)
Décodage en liste des codes de Goppa Binaires et réduction de clé de McEliece.

Résumé.

 

Vendredi 2 mars 2012
Ferenc Domes (Université de Nantes/ University of Vienna)
Rigorous enclosures of ellipsoids, and directed Cholesky factorizations.

Résumé.
Vendredi 9 mars 2012
Bernard Mourrain (INRIA, Sophia Antipolis)
Décomposition de tenseurs, opérateur de Hankel et bases de bord.

Résumé :
Les tenseurs apparaissent dans de nombreux problèmes comme objets mathématiques permettant de collecter des informations ou observations suivant différents "modes".
Leur décomposition en une somme minimale de tenseurs indécomposables peut être utilisée pour retrouver des caractéristiques intrinsèques ou géométriques "cachées dans les données".
Cette problématique  apparaît dans des domaines d'application aussi variés que le traitement du signal, l'analyse de données, la phylogénétique et même en théorie de la complexité  ou dans les codes correcteurs.
Quelques-uns de ces problèmes seront présentés ainsi que différentes notions de décomposition et de rang de tenseurs. Nous illustrerons par quelques exemples le comportement parfois surprenant de ces décompositions.
Nous décrirons l'approche de J.J.Sylvester pour calculer une décomposition de forme binaire et une extension plus récente pour des tenseurs multi-symétriques en dimension quelconque.
Des liens entre cette approche basée sur la dualité, certaines propriétés d'opérateurs de Hankel, des problèmes d'interpolation et le schéma de Hilbert de points seront détaillés.

 

Vendredi 16 mars 2012
Ainhoa Aparicio Monforte (Johannes Kepler University Linz)
Corps de series de Laurent formelles en plusieurs variables.

Résumé : Les séries de Laurent formelles à une indéterminée et à coefficients dans un corps commutatif K  forment, on le sait,  un corps commutatif pour la somme terme à terme  et le produit de Cauchy. Dans le cas de plusieurs variables,   l'exemple de la série de Laurent x+y\in K((x,y)) montre que c'est moins simple et que la notion d'inverse multiplicatif n'est pas bien définie. En partant de la construction introduite par Mc Donald pour les séries de Laurent à plusieurs variables et à support contenu dans un cône  rationnel strictement convexe, nous introduisons les ajustements nécessaires  permettant de définir les notions d'inverse et d'ordre pour une construction rigoureuse des corps de séries de Laurent formelles à plusieurs variables.  Ceci est un travail en commun avec Manuel Kauers (RISC, Linz).
Vendredi 23 mars 2012
Session de calcul formel pour l'Ecole Jeunes Chercheurs en Informatique Mathématique du 19 au 23 mars à Rennes
Vendredi 1er juin
Guillaume Quintin (LIX, Polytechnique)
A Lifting Decoding Scheme and Implementation of List Decoding

Résumé:
In the first part of the talk I will present a decoding algorithm based on a lifting decoding scheme. This leads to a unique decoding algorithm for Reed-Solomon (RS) codes over Galois rings with a very low complexity,
and a list decoding algorithm. I will show how to extend this scheme to RS codes over non commutative finite rings. If time permits I will show how to apply these techniques to interleaved RS codes. In the second part of the talk I will present the implementation of the Guruswami-Sudan list decoding algorithm in C (work in progress).

 



Archives 2010-2011

 

 

Vendredi 8 octobre
Daniel Perrucci (postdoc IRMAR)
Linear solving for sign determination

Abstract
The sign determination problem is the following one: given P_0, P_1, P_s in R[X], decide which are the sign conditions satisfied by P_1, ... , P_s at the real roots of
P_0. Given the ubiquity of this problem, it is important to have an algorithmic tool as efficient as possible to deal with it.
The current best known algorithm to solve the sign determination problem is based in two main ingredients: the computation of Sturm-queries and the resolution of linear systems (the Sturm-query between polynomials P, Q in R[X] is the diference between the number of real roots of P where Q takes a positive value and the number of real roots of P where Q takes a negative value).
In this talk, we will explain how this algorithm works and we will also introduce some specific method to solve the requiered linear systems which allows us to improve the overall complexity bound.

 

Vendredi 5 novembre
Vivien Dubois (DGA Rennes)
Cryptanalyse de cryptosystèmes basés sur des polynômes non commutatifs

Abstract.
Ten years ago, Ko et al. described a Diffie-Hellman like protocol based on decomposition with respect to a non-commutative semigroup law. Instantiation with braid groups had first been considered, however intense research on braid groups revealed vulnerabilities of the group structure and of the braid based DH problem itself.

Recently, Boucher et al. proposed a similar scheme based on a particular non-commutative multiplication of polynomials over a finite field. These so called skew polynomials have a well-studied theory and have many applications in mathematics and coding theory, however they are quite unknown in a cryptographic application.

In this paper, we show that the Diffie-Hellman problem based on skew polynomials is susceptible to a very efficient attack. This attack is in fact general in nature, it uses the availability of a one-sided notion of gcd and exact division. Given such tools, one can reduce the Diffie-Hellman problem to a linear algebra type problem.

 

Vendredi 26 novembre
Bruno Grenet (ENS Lyon)
Représentations de polynômes par déterminants symétriques

Résumé:
Dans un célèbre papier de 1979, Valiant prouve que le déterminant est universel pour les formules arithmétiques : tout polynôme sur un corps K donné par une formule peut être représenté par le déterminant d'une matrice "de petite taille" dont les coefficients sont des variables et des éléments de K. Ce résultat a ensuite été étendu aux circuits faiblement asymétriques indépendamment par Toda et Malod.

Dans ce travail, nous nous intéressons à la représentation de polynômes donnés par formules ou circuits faiblement asymétriques par des déterminants de matrices symétriques. En particulier, nous prouvons l'universalité de ces déterminants symétriques si le corps a une caractéristique différente de 2. Le cas de la caractéristique 2 fait l'objet d'un travail en cours avec Thomassé et Monteil (nous avons en particulier montré que les déterminants symétriques ne sont pas universels).

D'autre part, nous montrons que la VNP-complétude du permanent partiel en caractéristique 2 impliquerait un effondrement de la hiérarchie polynomiale, répondant ainsi par la négative à une question de Bürgisser.

Biblio : http://arxiv.org/abs/1007.3804

 

Vendredi 7 janvier
Fabrice Rouillier (INRIA)
Calculer efficacement les points singuliers d'une courbe plane et les multiplicités d'intersection associées.

Résumé
Le calcul des points singuliers d'une courbe et des multiplicités d'intersection associées est un verrou pour tout algorithme de calcul de topologie.

Nous proposons un nouvel algorithme permettant le calcul (paramétrisation rationnelle et isolation) des points singuliers et de leurs multiplicités d'intersection dont la caractéristique principale est d'associer des stratégies jusqu'alors opposées (sous-résultants vs bases de Gröbner) tout en préservant une complexité minimale.

Cet algorithme permet le calcul direct d'une décomposition équi-projetable par rapport à une coordonnée(*) des zéros de l'idéal définissant les points singuliers d'une courbe, chaque composante étant représentée par une paramétrisation rationnelle.

Nous montrerons que le nombre d'opérations arithmétiques nécessaires pour cet algorithme est au plus celui nécessaire au calcul d'une suite de sous-résultants et que la taille des coefficients intervenant dans le résultat est du même ordre que la taille des coefficients dans le discriminant de la courbe par rapport à l'une des variables.

Pour être complets, nous terminerons par quelques mots sur la partie "numérique" de la résolution avec les grandes lignes d'une nouvelle stratégie pour le calcul d'une approximation certifiée des solutions avec une grande précision.

(*) points de mêmes multiplicités dans les fibres

 

Vendredi 28 janvier
Guénaël Renault (LIP6)
Bases de Gröbner et symétries : le cas extrême du corps de décomposition.

Résumé
Lors de cet exposé, je commencerai par rappeler très brièvement la méthode générale pour le calcul du groupe de Galois d'un polynôme f unitaire à coefficients entiers. Je présenterai ensuite des algorithmes qui à partir de la connaissance du groupe de Galois de f calculent efficacement une base de Gröbner permettant de représenter son corps de décomposition K. Ces calculs sont basés sur l'utilisation des symétries (action du Groupe de Galois) pour faciliter les calculs d'interpolation et obtenir des relations sans coût. Je terminerai par montrer comment utiliser ces symétries pour obtenir une arithmétique
efficace dans K.
Cet exposé se base sur des travaux en collaboration avec S. Orange et K. Yokoyama.

 

 

Vendredi 18 février
Matthieu Legeay (IRMAR)
Utilisation du groupe de permutations d'un code-correcteur pour améliorer les algorithmes génériques de décodage

Résumé
Le décodage par maximum de vraisemblance d'un code-correcteur linéaire binaire est un des grands problèmes en théorie des codes-correcteurs. Il a été montré NP-difficile. Cependant, aucun des algorithmes de décodage génériques des codes-correcteurs d'erreurs ne prennent en compte le groupe de permutation des codes. On verra deux façons distinctes d'utiliser cette information sur le code pour améliorer les algorithmes existant.
La première idée fut lancée par MacWilliams en 1964 concernant les codes cycliques. Elle présentait un algorithme basée sur les ensembles d'information. Nous montrerons une évaluation théorique avec un cas particulier de permutation (travail réalisé en commun avec Christophe Chabot).
La seconde idée est basée sur l'utilisation d'un sous-code (\sigma-code) du sous-code idempotent d'un code. Nous montrerons des bornes sur la dimension du \sigma-code pour une permutation particulière \sigma et nous expliquerons comment utiliser cette information pour le décodage.

 

 

Vendredi 11 mars
Matyas Domokos (Alfréd Rényi Institute of Mathematics, Budapest)
Multisymmetric polynomials in dimension three

Abstract:
The polarizations of one relation of degree five and two relations of degree six minimally generate the ideal of relations among a minimal generating system of the algebra of multisymmetric polynomials in an arbitrary number of three-dimensional vector variables. In the general case of n-dimensional vector variables, a relation of degree 2n among the polarized power sums is presented such that it is not contained in the ideal generated by lower degree relations. The talk is partially based on joint work with Anna Puskas.

 

 

Vendredi 25 mars
Jérémy Le Borgne (IRMAR)
Polynômes tordus et phi-modules sur les corps finis.

Résumé :
On présentera un certain nombre de liens entre l'anneau des polynômes tordus sur un corps fini, et la théorie des phi-modules, qui apparaît dans l'étude de certaines représentations galoisiennes. En explorant ces liens, on verra notamment comment on peut obtenir en pratique un certain nombre d'informations sur les diverses factorisations d'un polynôme tordu, ainsi que sa "classe de similarité", ou encore comment calculer le plus petit multiple d'un polynôme tordu qui appartienne au centre de l'anneau.

 

 

Vendredi 1er avril
Luca De Feo (Postdoc IRMAR)
Principe de transposition et applications
(travail commun avec É. Schost et M. Boespflug)

Résumé. Le principe de transposition dit essentiellement que pour toute matrice M à coefficients dans un anneau R (non nécessairement commutatif) les fonctions v - vM et w - Mw, où v et w sont des vecteurs ligne et colonne respectivement, ont la même complexité en termes d’opérations algébriques dans R. Évidemment ceci n’est intéressant que lorsque la matrice M a une structure qui permet de calculer les produits en un nombre sous-quadratique d'opérations.

En calcul formel on connaît quatre opérations linéaires pour lesquelles ce principe donne des applications non triviales : il s'agit de la multiplication de polynômes, de la réduction modulaire, de l'évaluation polynomiale (parfois appelée composition modulaire) et de l'évaluation multipoint.

Du principe on peut obtenir une technique de transformation de code, initiée par Shoup et raffinée par la suite, qui donne les résultats les plus remarquables, aussi bien du point de vue de la théorie de la complexité que de l'implantation des systèmes de calcul formel.

L'automatisation de la transformation de code et la recherche d'autres applications non triviales ont motivé une étude du principe de transposition et de ses généralisations. Dans cet exposé je vais présenter les applications connues, aussi bien classiques que récentes, de ce principe ; ensuite je vais évoquer les avancées récentes sur la transposition de code et je vais terminer pour donner quelques pistes sur les généralisations possibles.

 

 

Vendredi 22 avril
Amadou Tall (Dakar)
Chaînes d'additions-soustractions et applications en cryptographie

 

 

Vendredi 13 mai
Roland Hildebrand (Grenoble)
Relaxations semi-définies par sommes de carrés abstraits

 

Vendredi 10 juin : exposé annulé !

Daniel Bembe (Universität München)
A certificate for Budan's theorem in  polynomial time

 

 

Vendredi 17 juin
Victoria Powers (Emory University, Atlanta)
Polya's Theorem with Zeros. 

 

Vendredi 1er juillet
Saugata Basu (Purdue University)
Baby step giant step road map algorithms

 

 

Archives 2001-2010

 

Année 2001-2002, Année 2002-2003, Année 2003-2004, Année 2004-2005, Année 2005-2006, Année 2006-2007, Année 2007-2008, Année 2008-2009, Année 2009-2010