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 :

Année 2014-2015 :

  • Vendredi 20 février à 10h30 salle 301 par Antoine Deza
    Titre : On the polynomial Hirsch conjecture and its continuous analogue
    Résumé :The simplex and primal-dual interior point methods are the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. In this talk, we highlight links between the edge and central paths, and between the diameter and the curvature of a polytope. We recall continuous results of Dedieu, Malajovich, and Shub, and discrete results of Holt and Klee and of Klee and Walkup, as well as related conjectures such as the Hirsch conjecture that was disproved by Santos. We also present analogous results dealing with average and worst-case behaviour of the curvature and diameter of polytopes, including a result of Allamigeon, Benchimol, Gaubert, and Joswig who constructed a counterexample to the continuous analogue of the polynomial Hirsch conjecture. Based on joint work with Tam ́as Terlaky (Lehigh), Feng Xie(Microsoft), and Yuriy Zinchenko (Calgary).
  • Vendredi 13 février à 10h30 salle 301 par Stefan Mengel
    Titre : Simulations de dynamique moléculaire ab initio: quels systèmes, pour quelles applications ?
    Résumé :Je présenterai la méthode de dynamique moléculaire ab initio dans la représentation de la fonctionnelle de la densité (DFT) et les applications d'intérêt dans notre groupe au laboratoire LAMBE de l'Université d'Evry val d'Essonne. Je montrerai comment nos simulations sont systématiquement employées pour aider à l'interprétation fine d'expériences de caractérisation d'états de la matière. Nous verrons en particulier des simulations de la spectroscopie anharmonique de molécules et clusters en phase gazeuse en lien avec les expériences IR-PD et IR-MPD, et des simulations d'interfaces solide d'oxide-eau liquide en lien avec des expériences de spectroscopie SFG. Nous verrons également quels développement venant de collaborations avec des équipes d'algorithmique (au PRISM) sont nécessaires pour automatiser certaines de nos analyses de trajectoires.
  • Vendredi 23 Janvier à 10h30 salle 301 par Marie-Pierre Gaigeot
    Titre : Simulations de dynamique moléculaire ab initio: quels systèmes, pour quelles applications ?
    Résumé :DNNFs are a class of Boolean circuits studied in the area of knowledge compilation in artificial intelligence where they serve as a target language into which knowledge bases are compiled. DNNFs form a very general language; in particular they generalize classical languages like OBDDs and DNF-formulas. While it was known that under standard complexity theoretic assumptions CNF formulas can generally not be compiled into DNNFs without a superpolynomial size blow-up, no concrete, unconditional lower bounds were known for DNNFs. In joint work with Simone Bova, Florent Capelli and Friedrich Slivovsky, we showed such a lower bound, proving that there are CNF-formulas of size linear in the number of variables that cannot be compiled into DNNFs of subexponential size. In this talk I will give and introduction into the area, explain our result, describe the hard CNF formulas and sketch some of the key parts of the proof.
  • Vendredi 16 Janvier à 10h30 salle 301 par Danièle Gardy
    Titre : Arbres-B et urnes de Polya
    Résumé :Après des rappels sur la structure d'arbre-B et les algorithmes associés, nous présentons une modélisation par urne de Polya des différents types de feuilles (ce sont par exemple les noeuds contenant les données dans une variante des arbres-B connue sous le nom d'arbres-B+). Le modèle des urnes de Polya fera également l'objet d'un rappel. Nous étudions le comportement asymptotique du nombre de feuilles avec un taux de remplissage fixé, et mettons en évidence une transition de phase -- classique dans les urnes de Polya, mais qui ne semble pas avoir été remarqué pour les arbres-B -- lorsque le paramètre m qui définit la capacité maximale d'un noeud varie : pour m = 60, la loi limite des fluctuations tend vers une variable aléatoire non classique.
  • Vendredi 9 Janvier à 10h30 salle 301 par Dietmar Berwanger
    Titre : A Frankenstein approach to games with delayed signals
    Résumé :We investigate distributed games where the information flow is perturbed by nondeterministic signalling delays. It is known that such perturbations make synthesis problems virtually usolvable, in the general case. On the classical model where signals are attached to states, tractable cases are rare and difficult to identify. Here, we propose a model where signals are detached from control states, and we identify a subclass on which equilibrium outcomes can be preserved, even if signals are delivered with a finitely bounded delay. To offset the perturbation, the synthesis procedure combines responses from a collection of equilibrium strategies for the instant-signalling game. This is joint work with Marie van den Bogaard.
  • Vendredi 12 Décembre à 10h30 salle 301 par Sylvain Peyronnet
    Titre : Découverte de communautés compactes dans des grands graphes
    Résumé :L’étude de réseaux sociaux n'est pas qu'un problème algorithmique : il est impossible de définir formellement ce que l'on cherche, et la taille des jeux de données implique des contraintes importantes sur la complexité algorithmique. Dans cet exposé, je présenterai des résultats, communs avec Jean Creusefond et Thomas Largillier, portant sur la détection de communauté dans des grands graphes.
  • Vendredi 31 octobre à 10h30 salle Archimède par Bertrand Le Cun.
    Titre : De la PRAM à un Branch and Bound sur cluster de SMP
    Résumé : Il m'a été demandé de parler de parallélisme, une sorte de "parallélisme pour les nuls". Je me propose donc de faire un tour horizon des problématiques posés par le parallélisme, en me limitant volontairement à la parallélisation de méthodes résolvant des problèmes d'optimisation. Nous aborderons par exemple des algorithmes parallèles de programmation dynamique sur machine théorique PRAM, mais aussi l'implantation d'algorithmes de Branch and Bound sur cluster de machines à mémoire partagée.
  • Vendredi 17 octobre à 10h30 salle 301 par Florent Capelli.
    Titre : #SAT et acyclicité d'hypergraphe
    Résumé : Le problème #SAT, de compter le nombre de solutions d'une formule donnée sous forme CNF, est connu pour être difficile tant à résoudre qu'à approximer. Afin de résoudre en pratique ce problème, il est intéressant de comprendre comment on peut tirer profit de certaines structures dans l'entrée pour obtenir des algorithmes paramétrés en temps polynomial. Une méthode qui a fait ses preuves consiste à associer un graphe ou un hypergraphe à une formule CNF et de regarder l'influence de certaines mesures de graphes classiques (treewidth, clique-width, acyclicité d'hypergraphe...) sur la complexité du problème. Dans cette présentation, nous essaierons de donner un aperçu général des différentes mesures de graphe que l'on peut exploiter efficacement et nous détaillerons plus en détail l'influence des différentes notions d'acyclicité d'hypergraphe pour ce problème.
  • Vendredi 21 Novembre à 10h30 salle 301 par Anne Bouillard.
    Titre : Perfect sampling in closed queueing networks
    Résumé :We investigate coupling from the past (CFTP) algorithms for closed queueing networks. The stationary distribution has a product form only in a very limited number of particular cases when queue capacity is finite, and numerical algorithms are intractable due to the cardinality of the state space. Moreover, closed networks do not exhibit any monotonic property enabling efficient CFTP. We derive a bounding chain for the CFTP algorithm for closed queueing networks. This bounding chain is based on a compact representation of sets of states that enables exact sampling from the stationary distribution without considering all initial conditions in the CFTP. The coupling time of the bounding chain is almost surely finite, and numerical experiments show that it is close to the coupling time of the exact chain.

Année 2013-2014:

  • 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!