Seminar

Le séminaire a lieu le vendredi à 10h30 en salle 301, environ deux fois par mois.

Le responsable est Yann Strozecki (cliquer sur le lien pour trouver les infos pour me contacter).

Quelques séminaires auquels les membres de l'équipe assistent aussi :

  • Le séminaire d'algorithmique du plateau de Saclay.
  • Le séminaire Digiteo

 

Liste des séances à venir :

 

Liste des séances passées :

    • Vendredi 11 octobre à 10h30 salle 301 par Pierre Coucheney.
      Titre : Aperçu sur les jeux stochastiques simples
      Résumé : Les jeux stochastiques simples (SSG) se jouent sur un graphe. Deux 
      joueurs, qui se partagent le contrôle des sommets avec le hasard, 
      déplacent un jeton de sommets en sommets en empruntant les arêtes du 
      graphe. Enfin, certains sommets sont des puits auxquels une valeur est 
      associée. L'objectif d'un joueur est de maximiser la valeur espérée du 
      puits atteint par le jeton, tandis que l'autre joueur cherche à la 
      minimiser. Il s'agit donc de jeux à somme nulle pour lesquels on peut 
      établir l'existence de stratégies optimales, le problème étant de 
      savoir si on peut les calculer en temps polynomial. 

      Dans cet exposé, je présenterai des propriétés des SSGs qui permettent 
      de calculer les stratégies optimales. Je parlerais plus en détail de plusieurs 
      sous-classes pour lesquelles des algorithmes polynomiaux existent, en 
      particulier celle des processus de décision markoviens.

    • Vendredi 25 octobre à 10h30 salle 301 par Lise Rodier.
      Titre : Distributed Selfish Algorithms for the Max-Cut game
      Résumé : Le problème Max-Cut consiste à diviser l'ensemble des sommets d'un graphe donné en deux parties telles que la somme des poids des arêtes qui traversent la partition est maximisée. Nous abordons le problème de calcul de coupe maximale locale dans les graphes non orientés de manière distribuée.

      Pour y parvenir, nous interprétons ces coupes maximales comme les équilibres de Nash pur d'un jeu de n joueurs à somme non nulle, chaque sommet étant un agent essayant de maximiser son propre intérêt.

      Un algorithme distribué peut alors être considéré comme le choix d'une politique pour chaque agent, décrivant comment adapter sa stratégie aux décisions des autres agents lors d'un jeu répété. Dans notre contexte, la seule information disponible pour chaque agent est le nombre de ses arêtes incidentes qui traversent ou non la coupe.

      Dans le cas général qu’est le cas pondéré, calculer un tel équilibre peut être démontré PLS-complet, comme c'est souvent le cas pour les jeux potentiels. Nous nous concentrons ici sur le cas (polynômial) non pondéré, mais avec la restriction supplémentaire que les algorithmes doivent être distribués comme décrit ci-dessus.

      Tout d'abord, nous décrivons un algorithme simple distribué pour les graphes généraux, et prouvons qu'il atteint une coupe maximale locale en 4Δ|E|, où E est l'ensemble des arêtes du graphe et Δ son degré maximal. Nous passons ensuite au cas du graphe complet, où nous montrons qu'une légère variation de cet algorithme atteint une coupe maximale locale en O (log log n).

      Nous concluons en donnant des résultats expérimentaux pour les graphes généraux.

    • Vendredi 8 Novembre à 10h30 en salle 301 par Jean Michel Fourneau
      Titre : Borne stochastique d'une chaîne de Markov donnée par une matrice de rang faible. 

      Résumé : 

 

    • Vendredi 29  Novembre à 10h30 en salle 301 par Hugo Gimbert (LABRI)

      Titre :Algorithmes pour les jeux stochastiques d'accessibilité avec observation partielle 
      Résumé : On présentera plusieurs résultats algorithmiques positifs et négatifs pour le calcul de la valeur des jeux stochastiques avec condition d'accessibilité et information partielle, en particulier :
      * l'existence de stratégies presque-sûrement ou positivement gagnantes est décidable, 
      * le problème de la valeur 1 est indécidable pour les jeux à 1 joueur, 
      * il est décidable pour certaines sous-classes de ces jeux. 

 

    • Vendredi 24 Janvier à 10h30 en salle 301 par Bruno Grenet (LICS)
      Titre : Algorithmes élémentaires pour la factorisation de polynômes lacunaires 
      Résumé : Nous nous intéressons à la factorisation des polynômes représentés sous forme lacunaire, c'est-à-dire par la liste de leurs monômes non nuls. Dans cette représentation, certains facteurs irréductibles peuvent être de taille exponentielle en la taille du polynôme. Ainsi, nous nous restreignons naturellement au calcul des facteurs de degré fixé. 
      Différents algorithmes existent pour ce problème lorsque le polynôme est à coefficient dans un corps de nombres, tous basés sur des résultats de théorie des nombres. Nous explorons ici une nouvelle approche basée uniquement sur les exposants des polynômes. Nous obtenons ainsi des algorithmes plus simples et plus rapides, et valables dans un plus grand nombre de situations, en particulier pour des polynômes à coefficients dans certains corps de caractéristique positive. 
      Notre approche consiste à borner la valuation de certaines familles de polynômes univariés, et est purement combinatoire par nature. Elle permet également de donner de nouveaux algorithmes pour le problème du test d'identité polynomiale. 
      Travail commun avec A. Chattopadhyay, P. Koiran, N. Portier & Y. Strozecki. 

 

    • Vendredi 7 Février à 10h30 en salle 301 par Pierre McKenzie de l'Université de Montréal
      Titre : Peut-on comprimer la mémoire utilisée lors d'un calcul polynomial? 
      Résumé : La théorie de la complexité du calcul cherche à quantifier les ressources (temps, mémoire, processeurs, etc.) requises à la résolution de tâches calculatoires. Cook en 1970 demandait si tout calcul polynomial peut être réorganisé de manière à réduire exponentiellement la quantité de mémoire nécessaire au calcul. Nous étudierons cette question sous l'angle d'un modèle de calcul appelé "branching program". À l'aide de tels programmes dédiés à la tâche d'évaluer un arbre ou un graphe acyclique (nous préciserons ce problème), nous développerons l'intuition qu'il n'est pas possible de comprimer la mémoire. Puis nous constaterons que malgré la force de cette intuition, nous ne savons fournir que des réponses très affaiblies à la question posée. Au passage, nous esquisserons une preuve de borne inférieure inventée en 1966 qui rencontre étonnamment la même barrière quadratique que toutes les méthodes inventées depuis. Nous terminerons avec un rapide état de l'art. (Résultats tirés en partie de Cook, McKenzie, Wehr, Braverman, Santhanam, Pebbles and branching programs for tree evaluation, ACM TOCT 2012.) 

 

    • Vendredi 14 Mars à 10h30 en salle 301 par Daniele Gardy
      Titre : Lambda-termes: énumération et statistiques 
      Résumé :  Les lambda-termes sont les objets de base du lambda calcul; syntaxiquement on peut les voir comme des arbres unaires-binaires colorés, ou comme des arbres de Motzkin dans lesquels on ajoute des arcs allant de certains noeuds unaires vers des feuilles. Nous nous intéresserons dans cet exposé aux questions suivantes: comment parler de lambda-terme aléatoire? et en premier lieu, compter les termes de taille donnée? dire quelle est la forme typique d'un terme? calculer la probabilité qu'un terme donné soit normalisable? Les réponses à ces questions se révèlent étonnament difficiles, et font apparaître des comportements totalement nouveaux: l'énumération des lambda-termes de taille donnée est encore un problème ouvert, pour lequel existent seules des bornes; nous présenterons les résultats obtenus pour deux classes de termes restreints: les termes d'arité fixe, ou de hauteur unaire bornée. 

 

    • Vendredi 28 Mars à 10h30 en salle 301 par Lélia Blin
      Titre : Algorithmes auto-stabilisants bavards 
      Résumé :  Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité évidente. Ce séminaire traite de l’auto-stabilisation, une méthode qui vise à concevoir des algorithmes distribués se « réparant d’eux-même » en cas de pannes transitoires pouvant impliquer toute modification arbitraire de l’état des processus. Plusieurs paramètres peuvent être pris en compte pour mesurer l’efficacité d’un algorithme auto-stabilisant, dont en particulier le temps de convergence et la complexité mémoire. L’importance du temps de convergence vient de la nécessité évidente pour un système de retrouver le plus rapidement possible un état valide après une panne. La nécessité de minimiser la mémoire vient, d’une part, de l’importance grandissante de réseaux offrant des espaces mémoires restreints, comme par exemple certains réseaux de capteurs, et, d’autre part, de l’intérêt de minimiser à la fois l’échange et le stockage d’information afin de limiter les potentialités de corruption de cette information. Lors de ce séminaire, nous traiterons de la minimisation de la mémoire au travers d'un exemple, à savoir le problème de l’élection d’un leader. Une borne inférieure de Ω(log n) bits de mémoire par noeud a été établie par Dolev, Gouda et Schneider (1999) pour ce problème fondamental. Cette borne n'est toutefois valable que pour des algorithmes silencieux, c'est-à-dire des algorithmes dont les registres ne sont plus modifiés lorsque le système a rejoint un état légitime. Nous verrons que, si l'on autorise l’algorithme à rester bavard (non-silencieux) même après avoir rejoint un état légitime, alors l’espace mémoire peut être amélioré d’un facteur au moins exponentiel. 

 

    • Vendredi 11 Avril à 10h30 en salle 301 par Frantisek Kardos
      Titre : Graphes fullerènes, couplages et cycles hamiltoniens 
      Résumé :  Un certains nombres de résultats sur la structure des graphes fullerènes (nombre de couplages, tailles des plus grands cycles ...) sont présentés dans cet exposé. 

 

    • Vendredi 16 mai à 10h30 en salle 301 par Thierry Monteil
      Titre : Pavages : quantifier l'aperiodicité d'un jeu de tuiles 
      Résumé :  Un jeu de tuiles de Wang est un ensemble fini de carrés unités dont on a colorié chaque côté. Un jeu de tuiles T pave le plan si celui-ci peut être recouvert par des translatés de copies d'éléments de T (selon Z^2), de sorte que les arêtes en contact de deux tuiles adjacentes soient de même couleur. Un jeu de tuiles est dit apériodique s'il pave le plan mais si aucun pavage obtenu n'est invariant par une translation. La plupart des jeux de tuiles apériodiques sont construits de façon autosimilaire (via une règle de substitution). Le but de cet exposé est d'introduire des invariants permettant de quantifier le niveau d'apériodicité d'un jeu de tuiles de Wang. L'un des invariants est de nature topologique, l'autre est métrique. Ils reposent sur la manière dont le jeu de tuiles pave d'autres objets que le plan. Ces invariants nous permettent de démontrer que les jeux de tuiles de Kari et Culik ne sont pas gouvernés par une construction autosimilaire, car trop apériodiques. 

 

  • Vendredi 6 juin à 11h00 en salle 301 par Olivier Marce
    Titre : Tout ce que vous aurez bien voulu savoir sur la 5G quand elle existera 
    Résumé :  

 Imprimer  E-mail

People

Permanent Members

David Auger MCF
Dominique Barth Professeur, MAGMAT team representative
Pierre Coucheney MCF 
Thu-Ha Dao-Thi CNRS researcher 
Jean-Michel Fourneau Professeur
Danièle Gardy Professeur
Leïla Kloul  MCF
Franck Quessette MCF
Dana Marinca MCF
Thierry Mautor MCF
Sandrine Vial MCF
Yann Strozecki MCF

 

 

 

 

 

 

 

 

 

MCF stands for "Maître de Conférences".

 

 

PhD Students

  advisors and co-advisors 
Farah Ait Salah J.-M. Fourneau & N. Pekergin & H. Castel-Taleb
Boubkeur Boudaoud D. Barth & T. Mautor
Mélanie Boudard J. Cohen & A. Denise
Amira Choutri D. Barth & L. Kloul
Mariem Krichen D. Barth & J. Cohen
Mohamed Lamine Lamali D. Barth
Cécile Mailler D. Gardy & B. Chauvin
Lise Rodier J. Cohen & D. Auger

 Advisors in blue are members of the MAGMAT project.

 

 

PostDocs

 

 

advisors

Vincent Reinhard

S. Vial

Vincent Armant

D. Gardy

Ebtissam Amar

L. Kloul

David Poulain

D. Barth

 Advisors in blue are members of the MAGMAT project.

 

 

 

 Imprimer  E-mail

Livres

Combinatoire

Combinatorics, Bollobàs (David)

Extremal Combinatorics, Jukna (David)

 

 

Apprentissage


Prediction, Learning, and Games, Cesa-Bianchi et al (David)

 

Complexité

Parametrized Complexity Theory, Flum and Grohe (David)

 

 

 Imprimer  E-mail

Equipe MAGMAT

Models, Algorithms, and Games for Molecules Analysis and Telecommunications

MAGMAT is a research project for the next five-year research plan (2013-2018) whose focus is on the complementarity and interactions between two fields of expertiseDiscrete Algorithms (Graph Theory, Discrete Mathematics, Complexity Theory, Algorithm Analysis) and Stochastic Models. Our focus is also on Algorithmic Game Theory, which is founded on these two domains.

We contribute to these fields of research and also apply them in two main fields of application, namely Dynamical Networks, and Molecular Structures.

The next figure summarizes the structure of our project.

diagramme englishThe MAGMAT project is based in the PRISM laboratory, in Université de Versailles Saint-Quentin-en-Yvelines, Campus de Sciences, Bâtiment Descartes.

 Imprimer  E-mail

DMC Firewall is a Joomla Security extension!