Laboratoire d'informatique de l'École polytechnique

News

Talk by Julian Gutierrez: «Nash Equilibrium and Bisimulation Invariance»

Speaker: Julian Gutierrez
Location: Salle Grace Hopper, Alan Turing building
Date: Wed, 27 Sep 2017, 11:00-12:00

The next Comète seminar will take place next Wednesday 27th of September 2017 at 11h00 in Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique). Julian Gutierrez, departmental lecturer in computer science at University of Oxford, will talk about "Nash Equilibrium and Bisimulation Invariance".

Abstract: Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a way involves computing the set of (Nash) equilibria in the game. However, we show that, with respect to the above model of strategies---the standard model in the literature---bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal formulae, nevertheless have fundamentally different properties from a game theoretic perspective. In this paper we explore the issues raised by this discovery, and investigate three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We also use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the literature.

Soutenance de thèse Michell Guzmán le 26/09/2017 à 15h

Speaker: Michell Guzmán
Location: Room Sophie Germain, Alan Turing building
Date: Tue, 26 Sep 2017, 15:00-17:00

Michell Guzmán will defend his Ph.D thesis entitled "On the Expressiveness of Spatial Constraint Systems" on Tuesday September 26th at 3 p.m. in the Sophie Germain room at the Alan Turing building.

Abstract: Epistemic, mobile and spatial behaviour are commonplace in today’s distributed systems. The intrinsic epistemic nature of these systems arises from the interactions of the elements of which they are comprised. Most people are familiar with digital systems where users share their beliefs, opinions and even intentional lies (hoaxes). Models of such systems must take into account the interactions with others as well as the distributed quality presented by them. Spatial and mobile behaviour are exhibited by applications and data moving across possibly nested spaces defined by, for example, friend circles, groups, and shared folders. Thus a solid understanding of the notion of space and spatial mobility as well as the flow of epistemic information is relevant in many models of today’s distributed systems. In order to analyze knowledge, space, and mobility in distributed systems, we expand upon the mathematically simple and elegant theory of constraint systems (cs), used to represent information and information change in concurrent systems. In the formal declara- tive model known as concurrent constraint programming, constraint systems provide the basic domains and operations for the semantic foundations of this model. Spatial constraint systems (scs’s) are al- gebraic structures that extend cs’s for reasoning about basic spatial and epistemic behaviour such as belief and extrusion. Both, spatial and epistemic assertions, can be viewed as specific modalities. Other modalities can be used for assertions about time, knowledge and even the analysis of groups among other concepts used in the specification and verification of concurrent systems. In this thesis we study the expressiveness of spatial constraint systems in the broader perspective of modal and epistemic behaviour. We shall show that spatial constraint systems are sufficiently robust to capture inverse modalities and to derive new results for modal logics. We shall show that we can use scs’s to express a fundamental epistemic behaviour such as knowledge. Finally we shall give an algebraic characterization of the notion of distributed information by means of constructors over scs’s.

Sémin'Ouvert : « Things, users, datacenters: enabling communication in the Internet of Everything » par Juan-Antonio Cordero-Fuertes

Speaker: Juan-Antonio Cordero-Fuertes
Location: Bât. Turing, salle G. Kahn
Date: Jeu. 21 sept. 2017, 14h30-15h30

Development of wireless networking technologies and Internet connectivity, improvement of computational capacities and availability of cheap, powerful connectable devices has empowered a substantial shift in the usage of the Internet, the emergence of new applications and possibilities and, tied to that, new challenges and needs on the Internet ecosystem. This presentation explores some of the leading trends in this transformation, and presents some contribution in some of the related research problems. In particular, the presentation focuses on the users content consumption by way of denser and broader Internet access networks, the wide-scale deployment of connected sensoring and monitoring “things”, that allow digitisation of building, cities, public infrastructures or facilities (energy grid, transport networks), and the optimization of core Internet infrastructures (datacenters) to support data collection and processing from the “Internet of things” and efficient content distribution to users.

Attribution d'une bourse européenne pour le projet EXPROTEA

Maks Ovsjanikov de l'équipe Stream s'est vu attribuer une ERC Starting Grant pour son projet EXPROTEA d'exploration de relations dans des données structurées à l'aide de cartes fonctionnelles.

Talk by Rob van Glabbeek: «Congruence Formats in Structural Operational Semantics»

Speaker: Rob van Glabbeek, Data61, CSIRO and UNSW, Sydney, Australia
Location: Room Henri Poincaré, Alan Turing building
Date: Tue, 12 Sep 2017, 14:00-15:00

The next Comète seminar will take place on Tuesday 12th of September 2017 at 14h00 in Salle Henri Poincaré (LIX - Alan Turing building, École Polytechnique). Rob van Glabbeek, chief research scientist at Data61, CSIRO and conjoint professor at the University of New South Wales, Sydney, Australia, will talk about "Congruence Formats in Structural Operational Semantics".

Abstract: This talk presents an overview on work on syntactic checks on structural operational language specifications that ensure that a certain semantic equivalence or preorder is a (pre)congruence. This is vital for compositional system verification. I will focus on strong and weak bisimilarity, and its divergence respecting variants. The languages I consider may have, besides constants and operators, also a recursion construct. For the latter I distinguish two kinds of congruence requirements: lean and full.

Soutenance de thèse d'Amélie Héliou: «Conformations moléculaire et théorie des jeux»

Speaker: Amélie Héliou
Location: Amphi. Sophie Germain, bâtiment Alan Turing
Date: Jeu. 31 août. 2017, 14h00-16h00

Amélie Héliou soutiendra sa thèse intitulée «Conformations moléculaire et théorie des jeux» le jeudi 31 août 2017 dans l'amphithéâtre Sophie Germain du bâtiment Alan Turing.

Résumé: Les protéines et acides ribonucléiques sont les principaux acteurs de nombreux processus cellulaires. Comprendre leurs fonctions, structures et interactions est un challenge important. Les méthodes expérimentales fournissent des informations sur la structure et la dynamique des molécules. Cependant les méthodes expérimentales sont limitées par le nombre de molécules qu’elles peuvent observer et les moyens qu’elles requièrent. Les méthodes de prédiction permettent d’obtenir des informations structurelles de façon quasi-automatique. Pour s’assurer de leur fiabilité, elles sont testées sur des données expérimentales. Nous présentons une procédure basée sur la cinétique inverse pour trouver une transition entre deux conformations d’un ARN tout en conservant sa structure secondaire. Nous obtenons des résultats comparables à l’état de l’art, ce qui montre que notre sélection des degrés de liberté est pertinente. De plus, nous utilisons des données partielles, ce qui permet d’utiliser différents types de résultats expérimentaux. Nous abordons aussi le problème du repliement protéique par une approche de théorie des jeux. Nous représentons une protéine par un jeu où les joueurs sont les acides aminés et les stratégies, les angles dièdres. La prédiction de structure peut alors être vue comme la recherche d’un équilibre dans un jeu multi-joueur où les fonctions d’utilité correspondent à la qualité du repliement. Nous montrons que l’algorithme de non-regret, appelé Hedge, garantit l’élimination des stratégies dominées et la convergence locale vers un équilibre de Nash. Puis, en limitant notre analyse aux jeux de potentiel, nous montrons qu’une classe plus large d’algorithmes, les algorithmes de régularisation, convergent vers un équilibre de Nash presque surement.

Soutenance de thèse d'Anatolii Kostrygin: «Analyse précise des algorithmes épidémiques»

Speaker: Anatolii Kostrygin
Location: Salle Grace Hopper, bâtiment Alan Turing
Date: Mar. 29 août. 2017, 14h00-16h00

Anatolii Kostrygin soutiendra sa thèse intitulée «Analyse précise des algorithmes épidémiques» le mardi 29 août 2017 à 14h00 dans la salle Grace Hopper.

Résumé: Dans cette thèse nous étudions le problème de propagation de rumeur, c.-à-d. la dissémination collaborative, robuste et anonyme d’une information entre tous les agents d’un système distribué. Ce problème est à la base de nombreux algorithmes de communication sur des réseaux de capteurs sans-fil ou des réseaux mobiles ad-hoc. Il est aussi une brique centrale pour les nombreux algorithmes distribués avancés.

Nous proposons une méthode générale d'analyse des protocoles de la propagation de rumeur dans les graphes complets. Contrairement aux résultats précédents basés sur la structure précise des processus étudiés, notre analyse est basée sur la probabilité et la covariance des évènements correspondants au fait qu'un agent non-informé s'informe. Cela nous permet de reproduire les résultats basiques concernant les protocoles classiques de push, pull et push-pull ainsi qu'analyser les certaines variations telles que les échecs de communications ou les communications multiples réalisées par chaque agent. De plus, nous sommes capables d'analyser les certains modèles dynamiques quand le réseaux forme un graphe aléatoire échantillonné à nouveau à chaque étape. Notre méthode nous permet de déterminer l'espérance du temps de la diffusion à une constante additive près, ce qu'il est plus précis que la plupart des résultats précédents. Nous montrons que la déviation du temps de la diffusion par rapport à son espérance est inférieure d'une constante r avec la probabilité au moins 1 − exp(Ω(r)).

Nous discutons d'une hypothèse classique que les agents peuvent répondre à plusieurs appels entrants. La restriction à un seul appel entrant par agent provoque un ralentissement important de la diffusion pour un protocole de push-pull. Nous proposons une variation simple du protocole de push-pull qui rétablit une phase double logarithmique à nouveau et donc le nombre de messages passés redescend sur sa valeur optimal.

Soutenance de thèse d'Alice Héliou

Speaker: Alice Héliou (Amib)
Location: Salle Sophie Germain, bâtiment Alan Turing
Date: Lun. 10 juill. 2017, 14h30-16h00

Alice Héliou (équipe Amib) soutiendra sa thèse intitulée Analyse des séquences génomiques : Identification des ARNs circulaires et calcul de l'information négative, le lundi 10 juillet à 14h30 en salle Sophie Germain du bâtiment Alan Turing.

Résumé : Le développement des techniques de séquençage à haut débit a permis de nombreuses avancées dans les domaines de la biologie et de la santé. Les données sont produites en grande quantité à des coûts toujours plus faibles, cependant leur stockage et leurs analyses demeurent de vastes sujets de recherche.

Dans un premier temps nous avons étudié l'identification des ARNs circulaires à partir des données de séquençage. L'alignement de ces données, appelées des lectures, pour identifier les ARNs circulaires est particulier. En effet, avant d'être séquencés les ARNs sont fragmentés aléatoirement en morceaux de taille environ 100. Ceux-ci sont ensuite lus lors du séquençage, on obtient ainsi les lectures. La jonction d'un ARN circulaire peut se retrouver à des positions aléatoires sur les lectures. Celles-ci s'alignent donc seulement partiellement à deux endroits sur le génome, au lieu d'avoir un match global. Nous avons proposé une nouvelle méthode permettant d'identifier les ARNs circulaires chez les Archées et les Bactéries. Nos résultats ont permis de montrer l'implication de la ligase de la famille Rnl3 dans la circularisation des ARNs chez l'archée Pyroccoccus Abyssi.

Dans un second temps, nous avons abordé de façon plus théorique l'analyse des séquences génomiques. L'analyse de ces séquences repose généralement sur leur alignement ou sur la distribution des mots présents. Nous nous sommes intéressés à une approche duale de celles-ci, en nous concentrant sur ce qui est absent, l'information négative. Plus précisément nous avons élaboré des algorithmes pour calculer les mots qui sont absents d'une séquence mais dont tous les facteurs sont présents, les mots absents minimaux. Nos algorithmes ont tous des complexités linéaires en temps et en espace, mais ils diffèrent sur le compromis entre temps de calcul et quantité de mémoire interne utilisée.

Soutenance de thèse de Thibault Manneville

Speaker: Thibault Manneville
Location: Amphi Sophie Germain, bâtiment Alan Turing
Date: Jeu. 6 juill. 2017, 14h00-15h30

Thibault Manneville soutiendra sa thèse intitulée Généralisations géométriques et combinatoires de l'associaèdre le jeudi 6 juillet 2017 à 14h dans l'amphithéâtre Sophie Germain du LIX (bâtiment Alan Turing).

Résumé: L'associaèdre se situe à l'interface de plusieurs domaines mathématiques. Combinatoirement, il s'agit du complexe simplicial des dissections d'un polygone convexe (ensembles de diagonales ne se croisant pas deux à deux). Géométriquement, il s'agit d'un polytope dont les sommets et les arêtes encodent le graphe dual du complexe des dissections. Enfin l'associaèdre décrit la structure combinatoire qui définit la présentation par générateurs et relations de certaines algèbres, dites « amassées ». Du fait de son omniprésence, de nouvelles familles généralisant cet objet sont régulièrement découvertes. Cependant elles n'ont souvent que de faibles interactions. Leurs études respectives présentent de notre point de vue deux enjeux majeurs : chercher à les relier en se basant sur les propriétés connues de l'associaèdre ; et chercher pour chacune des cadres combinatoire, géométrique et algébrique dans le même esprit. Dans cette thèse, nous traitons le lien entre combinatoire et géométrie pour certaines de ces généralisations : les associaèdres de graphes, les complexes de sous-mots et les complexes d'accordéons. Nous suivons un fil rouge consistant à adapter, à ces trois familles, une méthode de construction des associaèdres comme éventails (ensembles de cônes polyédraux), dite méthode des d-vecteurs et issue de la théorie des algèbres amassées. De manière plus large, notre problématique principale consiste à réaliser, c'est-à-dire plonger géométriquement dans un espace vectoriel, des complexes abstraits. Nous obtenons trois familles de nouvelles réalisations, ainsi qu'une quatrième encore conjecturale dont les premières instances constituent déjà des avancées significatives. Enfin, en sus des résultats géométriques, nous démontrons des propriétés combinatoires spécifiques à chaque complexe simplicial abordé.

Talk by Jean-Éric Pin: «Dual space of a lattice as the completion of a Pervin space»

Speaker: Jean-Éric Pin (Irif)
Location: Room Grace Hopper, Alan Turing Building
Date: Fri, 30 Jun 2017, 11:00-12:00

Abstract: In this survey lecture, I will mainly cover well-known results from a new angle. A Pervin space is simply a set equipped with a lattice of subsets. This notion suffices to define a natural notion of completion which appears to be the dual of the original lattice. One can then show that any lattice of subsets can be described by a set of inequations of the form u <= v, where u and v are elements of its dual space. Applications to formal languages and complexity classes will be given.

Parution du livre Asymptotic Differential Algebra and Model Theory of Transseries

Nous avons le plaisir de vous annoncer la parution du livre Asymptotic Differential Algebra and Model Theory of Transseries dans la série Annals of Mathematics Studies co-écrit par Matthias Aschenbrenner, Lou van den Dries et Joris van der Hoeven. Voir http://press.princeton.edu/titles/11044.html.

Invitation au Congrès International des Mathématiciens 2018

Joris Van der Hoeven, avec ses coauteurs Matthias Aschenbrenner (UCLA) et Lou van den Dries (UIUC), a été invité pour le prochain congrès international des mathématiciens (ICM 2018) à Rio de Janeiro. Ils exposeront entre autres les résultats récents de leur livre sur l'algèbre différentielle asymptotique et la théorie des modèles des transséries.

Soutenance de thèse d'Olivier Wang

Speaker: Olivier Wang
Location: Salle Gilles Kahn, bâtiment Alan Turing
Date: Wed, 28 Jun 2017, 14:00-15:30

Olivier Wang soutiendra sa thèse intitulée Analytics Learning for Rule-Based Systems le vendredi 28 juin 2017 à 14h00 dans la salle Gilles Kahn du bâtiment Alan Turing

Résumé: Les Règles Métiers (Business Rules en anglais, ou BRs) sont un outil communément utilisé dans l’industrie pour automatiser des prises de décisions répétitives. Le problème de l’adaptation de bases de règles existantes à un environnement en constante évolution est celui qui motive cette thèse. Des techniques existantes d’Apprentissage Automatique Supervisé peuvent être utilisées lorsque cette adaptation se fait en toute connaissance de la décision correcte à prendre en toute circonstance. En revanche, il n’existe actuellement aucun algorithme, qu’il soit théorique ou pratique, qui puisse résoudre ce problème lorsque l’information connue est de nature statistique, comme c’est le cas pour une banque qui souhaite contrôler la proportion de demandes de prêt que son service de décision automatique fait passer à des experts humains. Nous étudions spécifiquement le problème d’apprentissage qui a pour objectif d’ajuster les BRs de façon à ce que les décisions prises aient une valeur moyenne donnée.

Séminaire blockchain le 22 juin : deux exposés, Romaric Ludinard et Julien Prat

Location: Salle Gilles Kahn, bâtiment Alan Turing
Date: Jeu. 22 juin. 2017, 11h00-15h00

La prochaine séance du séminaire blocksem à l'École polytechnique se tiendra le 22 juin, salle Gilles Kahn (rdc bâtiment Turing, INRIA). Le programme complet et les résumés des exposés sont sur le site du séminaire.

11:00-12:00 Romaric Ludinard, ENSAI / CREST. Accord en système distribué.

12:00-13:30 Repas dans le hall du bâtiment.

13:30-15:00 (format mini cours) Julien Prat, CNRS, CREST. A Model of the Bitcoin Miners Market avec Walter Benjamin.

Amaury Pouly remporte le prix Ackermann 2017

Amaury Pouly est le lauréat 2017 du prix Ackermann (Ackermann Award).

Le prix Ackermann est le prix de l’EACSL (European Association for Computer Science Logic) qui récompense chaque année une thèse exceptionnelle dans les domaines de la Logique et la science Informatique. Le prix sera remis et présenté à la conférence annuelle de l’association (CSL’2017).

La thèse d’Amaury Pouly démontre en particulier que l’on peut caractériser le temps polynomial (la classe P de la question P=NP) comme les solutions de longueur polynomiale d’équations différentielles polynomiales. Ce résultat ouvre la voie à reformuler certaines questions et concepts de l’informatique théorique en termes d'équations différentielles ordinaires polynomiales. Il revisite par ailleurs les modèles de calcul analogiques et démontre que les ordinateurs analogiques et digitaux ont en réalité la même puissance de calcul, à la fois au niveau de ce qu’ils peuvent calculer (calculabilité) et de ce qu’ils peuvent résoudre en temps polynomial (complexité).

Amaury a effectué sa thèse en cotutelle entre le Laboratoire d’informatique de l’X (LIX), UMR Ecole Polytechnique et CNRS en France, et l’Université d’Algarve au Portugal. Ses directeurs de thèse sont Olivier Bournez, en France, et Daniel Graça, au Portugal.