Groupe de Travail CPU/Axe 3



Année 2012-2013



Année 2013-2014


Si vous souhaitez recevoir les annonces des exposés contactez Christine Bachoc



Sylvia Bianchi 4/10/2013 Polyhedra associated with identifying codes
The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size. In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for particular graphs. Also we describe facet defining inequalities for the identifying code polyhedron of some bipartite graphs and odd cycles. Finally, we discuss further lines of research in order to obtain other facet defining inequalities to be added to linear relaxations of the identifying code polyhedron, in order to obtain suitable cutting planes to be used in a B\&C framework.
Salle 76, Labri, 14h-15h
Gilles Zémor 25/10/2013 Graphes sur des surfaces et codes quantiques
Les cycles d'un graphe définissent un code correcteur simple et décodable efficacement. Les analogues quantiques d'un code des cycles d'un graphe sont constitués de la donnée simultanée de deux codes des cycles, l'un associé à un graphe dessiné sur une surface, et l'autre associé à son graphe dual. Soumettre un code des cycles à un canal à effacements revient graphiquement à regarder des sous-graphes aléatoires. On ne peut pas décoder si et seulement si le sous-graphe contient un cycle. Dans le cas quantique, l'événement pertinent survient lorsque le sous-graphe contient un cycle non-homologue à zéro. L'étude de ce phénomène permet d'obtenir une formule semi-explicite, permettant d'avoir des bornes supérieures non-triviales, sur la probabilité critique de la percolation sur les pavages réguliers auto-duaux du plan hyperbolique.
Travail commun avec Nicolas Delfosse.
Salle 76, Labri, 14h-15h
Renaud Coulangeon 5/11/2013 Algorithmes de Voronoi et groupes d'unités
On présentera certains aspects d'un travail en cours avec Gabriele Nebe (RWTH Aachen), sur le calcul du groupe des unités d'un ordre maximal d'une algèbre semi-simple sur Q. Les méthodes utilisées reposent sur une combinaison de la théorie de Bass-Serre des "graphes de groupes" et de différents avatars de l'algorithme de Voronoi pour les formes quadratiques. L'exposé portera plus particulièrement sur la description d'un algorithme pour le calcul des classes de conjugaison des sous-groupes finis maximaux d'un tel groupe d'unités.
Salle 385, IMB, 10h-11h
Renaud Coulangeon 22/11/2013 Graphes de groupes (I)
Salle 385, IMB, 13h-14h
Mate Matolcsi 22/11/2013 Maximal cliques in Paley graphs
For infinitely many primes p = 4k + 1 we give a slightly improved upper bound for the maximal cardinality of a subset B of Zp such that the difference set B - B contains only quadratic residues. Namely, instead of the "trivial" bound |B| <= \sqrt{p} we prove |B| <= \sqrt{p} - 1, under suitable conditions on p. The new bound is valid for approximately three quarters of the primes p = 4k + 1. Joint result with C. Bachoc and I. Z. Ruzsa.
Salle 178, Labri, 14h-15h
Renaud Coulangeon 29/11/2013 Graphes de groupes (II)
Salle 385, IMB, 13h-14h
Soline Renner 13/12/2013 High-Order Masking by Using Coding Theory and its Application to AES
To guarantee that some implementation of a cryptographic scheme is secure against side channel analysis, one needs to formally prove its leakage resilience. A relatively recent trend is to apply methods pertaining to the field of Multi-Party Computation: in particular this means applying secret sharing techniques to design masking countermeasures. It is known besides that there is a strong connection between secret sharing schemes and error-correcting codes, namely every linear code gives rise to a linear secret sharing scheme. However, the schemes mostly used in practice are the so-called Boolean masking and Shamir's secret sharing scheme and it is widely thought that they are the most adapted to masking techniques because they correspond to MDS codes that are in some sense optimal. We present alternative masking techniques that rely on {\em non-MDS} linear codes: these codes are non-binary but have an underlying binary structure which is that of a \textit{self-orthogonal binary} code. Their being non-MDS is compensated by the fact that the distributed multiplication procedure is more efficient than with MDS codes due to an efficient encoding process and that the distributed computation of squares comes at almost no cost. In protecting AES against high-order side channel analysis, this approach is more efficient than methods using Shamir's secret sharing scheme and competitive with Boolean masking.
Salle 385, IMB, 14h-15h
Frédérique Oggier (NTU, Singapour) 09/01/2014 Le codage pour le stockage distribué de données
Salle 385, IMB, 14h-15h
Nicolas Delfosse 14/02/2014 Une introduction au calcul quantique tolérant aux fautes
Alors que les composants classiques sont suffisamment fiables, chaque manipulation d'un bit quantique a une probabilité non négligeable d'introduire une erreur. Ceci rend l'application d'une porte quantique délicate. Je présenterai différentes techniques permettant de transformer un circuit quantique en un circuit quantique tolérant aux fautes.
Salle 178, Labri, 14h15-15h15
Oriol Serra (UPC, Barcelone) 31/03/2014 Algebraic Removal Lemma
The removal lemma is a combinatorial result which, in its simpler form, says that a graph with n vertices and o(n^3) triangles can be made triangle free by deleting o(n^2) edges. It was used by Ruzsa and Szemerédi to provide a simple proof of Roth's theorem on 3-term arithmetic progressions in dense sets of integers. An analogous algebraic statement was formulated by Green in terms of solutions of linear equations in abelian groups. In the talk I will report on some contributions made jointly with Dan Král' and Lluís Vena to this algebraic version for linear systems in abelian groups and some consequences in arithmetic Ramsey theory. The latter include a version of Szemerédi theorem on arithmetic progressions in dense sets of finite abelian groups.
Salle 178, Labri, 14h-15h
Christine Bachoc 26/05/2014 Le codage de réseau aléatoire : une introduction
Dans cet exposé on expliquera comment le taux de transmission au travers d'un réseau de communication peut être augmenté par rapport aux taux de transmission atteints par simple routage si on autorise les noeuds du réseaux à effectuer des calculs algébriques sur les données transmises. On montrera que le codage linéaire permet d'atteindre la capacité du réseau dans le cas d'une unique source, si le corps de base des paquets transmis est assez grand.
Salle 178, Labri, 14h-15h
Thomas Bellitto 04/07/2014 Codes séparateurs et surveillance de traffic
Cette présentation porte sur les problèmes de séparation dont un exemple bien étudié au Labri est celui de code identifiant dans un graphe. Dans le cas général, il s'agit de trouver un ensemble de propriétés aussi petit que possible permettant de distinguer un ensemble d'individus donné. Nous étudierons des modèles basés sur différentes structures combinatoires et comparerons leur expressivité. Nous nous intéresserons ensuite au problème de surveillance de trafic dans un réseau qui consiste à déterminer où placer des capteurs sur les arcs d'un graphe pour pouvoir reconstituer le chemin suivi par un marcheur. Nous exprimerons ce problème comme un problème de séparation en introduisant un nouveau modèle : la séparation sur un langage. Nous étudierons ensuite ce nouveau problème et développerons des algorithmes de résolution, particulièrement sur les instances spécifiques issues du problème de surveillance de trafic.
Salle 178, Labri, 14h-15h
Akka Zemmari 11/07/2014 Coloration distribuée et probabiliste
La coloration est un problème classique de la théorie des graphes et de l'algorithmique distribuée. Dans cet exposé, je ferai un résumé des résultats obtenus récemment pour la résolution de ce problème. On montrera comment obtenir une (Delta+1)-coloration en O(log n) rondes et en utilisant des messages à 1 bit. Nous montrerons que l'algorithme est optimal et ce en utilisant des revêtements de graphes. Dans le cas où le réseau est un anneau, nous verrons qu'en utilisant la transformée de Mellin, il est possible de donner la valeur exacte de la constante cachée dans le O(log n).
Salle 178, Labri, 14h-15h
Gilles Zémor 10/10/2014 La méthode des atomes en théorie des graphes et en théorie des nombres
Les atomes d'un graphe ont été introduits pour étudier leur connectivité. Depuis, la méthode atomique ou isopérimétrique a été transposée en combinatoire additive pour obtenir des caractérisations d'ensembles de petite somme dans les groupes. Nous passerons en revue ces connexions et aborderons une application récente, obtenue avec Oriol Serra et Christine Bachoc, sur la caractérisation, dans des extensions de corps, d'espaces vectoriels dont le produit a une petite dimension.
Salle 178, Labri, 14h-15h
Alain Couvreur (INRIA et LIX) 9/12/2014 Une attaque polynomiale du schéma de McEliece basé sur les codes de Goppa 'sauvages'
Le schéma de McEliece est un schéma de chiffrement basé sur les codes correcteurs d'erreurs dont la sécurité repose sur la difficulté à décoder un code aléatoire. Parmi les différentes familles de codes algébriques proposées pour ce schéma, les codes de Goppa classiques sont les seuls à résister à toutes les attaques algébriques, et ce, depuis près de 35 ans. Dans cet exposé, je présenterai une attaque d'un genre nouveau, dite "par filtration" qui permet de retrouver la structure d'un code de Goppa "sauvage" (Wild Goppa code) construit à partir d'une extension de corps quadratique. Cette attaque consiste à utiliser des propriétés multiplicatives du code pour en calculer une filtration (i.e. une famille de sous-codes emboités) dont chaque élément est un code de Goppa classique. Les propriétés algébriques de cette filtration permettent ensuite de retrouver entièrement la structure du code utilisé comme clé publique. Cette attaque a été implémentée en Magma et permet de casser en moins d'une heure des clés proposées par Bernstein, Lange et Peters dont la sécurité était estimée supérieure à 128 bits (Wild McEliece, SAC 2010). Depuis l'introduction du schéma de McEliece, c'est la première attaque polynomiale sur des codes de Goppa classiques n'ayant aucune symétrie apparente.
(Travail commun avec Ayoub Otmani et Jean-Pierre Tillich)
Salle 386, IMB, 10h-11h