Archives du séminaire de calcul formel et complexité
2011-2012

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

(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)

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.

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.
 

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


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

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.

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 2012
Guillaume Quintin (LIX, Polytechnique)
A Lifting Decoding Scheme and Implementation of List Decoding

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).