Séminaires SIESTE

SIESTE :

Séminaire d’Informatique pour les Etudiants, Scientifiques, et Tous ceux que l’informatique intéresse à l’ENS Lyon

  • Public et Objectif: Ouvert à tous. Ce séminaire est obligatoire pour les L3, et recommandé pour les M1.
    Ce séminaire propose une introduction à un domaine de recherche actuel d’une manière accessible aux non spécialistes et aux étudiants. Même les chercheurs expérimentés peuvent être intéressés!
  • Contact:Suivi administratif du séminaire: Orianne Pelletier
    Organisation du séminaire: Pascal Koiran
  • Horaire et lieu: Les mardi à 13h30. Nous ferons le SIESTE en amphi B (campus Monod, 3ème étage du bêtiment principal). Des rafraichissements seront ensuite proposés en salle passerelle du quatrième étage. Le public pourra alors discuter avec l’orateur.
  • Dates:
    • 13 février. Matthieu Moy.
    • 6 février 2018. Warwick Tucker.
    • 28 novembre. Bruno Salvy: Équations différentielles linéaires : une structure de données.
    • Abstract: De nombreuses informations concernant les solutions d’équations différentielles linéaires peuvent être calculées directement à partir de l’équation. Il faut donc se guérir de la tentation de «résoudre», et utiliser ces équations comme une structure de données à laquelle des algorithmes s’appliquent. Ces algorithmes sont de natures diverses : certains extraient de l’information, d’autres au contraire calculent des équations, puisque c’est la structure de données utilisée. L’exposé présentera un panorama d’algorithmes dans ce domaine, comme le calcul rapide de la factorielle, de décimales de pi, d’intégrales ou de sommes, ou la preuve automatique d’identités.

    • 7 novembre. Suliann Ben Hamed : From motor brain-machine interfaces to cognitive brain-machine interfaces (powerpoint of her presentation here).
    • Abstract: In the last years, tremendous advances have been achieved in the development of neuroprostheses that allow patients with advanced motor deficits to recover a certain degree of independence. The concept behind these motor brain-machine interfaces is that patients use their motor cortical activity to control ever more complex robotic arms to interact with their environment. In contrast, in spite of the large range of potential applications in the field of cognitive disabilities, only smaller advances have been achieved in the field of cognitive brain-machine interfaces, due to specific methodological challenges. In a first part of this presentation, I will cover the general methods and recent advances in “mind reading”, i.e. in the ability to extract ongoing information from cortical activity. In a second part of my presentation, I will illustrate cognitive brain machine interfaces through the real-time tracking of covert spatial attention from dense cortical neuronal recordings in a non-human primate model of human cognition. I will highlight the strength of this approach, explain the current challenges that need to be faced and discuss possible applications, including neurofeedback.

    • 24 octobre. Rémi Watrigant. Détecter les parties denses d’un graphe : problème facile ou difficile ?
    • *** Changement de salle : amphi Schrödinger. ****

      Résumé : Dans cet exposé, nous tenterons de comprendre la complexité algorithmique intrinsèque de quelques problèmes dans les graphes, et en particulier d’étudier la frontière parfois assez mince entre les problèmes polynomiaux et NP-difficiles. Notre cas d’étude sera le problème de la recherche de structures denses dans des graphes, un problème important tant du point de vue théorique que pratique. Nous nous pencherons également sur certaines classes de graphes dans lesquelles des outils algorithmiques peuvent permettre de résoudre en temps polynomial des problèmes difficiles dans le cas général, et terminerons par des questions encore ouvertes sur ce sujet.

    • 17 octobre 2017. Chien-Chung Huang : Matching under preferences: a case study in popular matching.
    • *** Changement de salle : amphi Schrödinger. ***

      Résumé : Let G be a bipartite graph, where both sides (think boys and girls, or people and houses) have preferences. A matching M is said to be popular if there is no other matching M’ that is preferred by the majority of the people. In this talk, we give a survey on the status of the complexity of computing a popular matching and then we give a more detailed presentation on the extension of mixed popular matching and its associated polytope.

    • 10 octobre 2017. Olivier Bournez : Machines et calculs analogiques, la revanche.
    • Résumé : Les ordinateurs actuels sont digitaux: ils travaillent sur des bits, des 0 et des 1. Cependant, historiquement, ils ont cohabité assez longuement avec des machines analogiques: ces dernières, mécaniques, électronique, ou électromécaniques, travaillaient sur des quantités continues, comme des angles ou des tensions. Elles ont disparu progressivement après l’invention du transistor, et la victoire des partisans du digital sur les partisans de l’analogique.

      Dans cet exposé, on reviendra sur certaines des machines analogiques, et sur leur histoire riche, souvent injustement oubliée par la plupart des récits de l’histoire de l’informatique, qui font souvent comme si ce n’étaient pas les premières machines de calcul programmables.

      On discutera de leur puissance, et on verra qu’en réalité elles ont la même puissance de calcul que les modèles actuels, et qu’elles permettent de revisiter en 2017 l’informatique théorique et les mathématiques de façon élégante et inattendue.

    • 19 septembre 2017. Gabriel Kerneis (Google) : Atteindre un haut niveau de fiabilité pour un grand nombre d’utilisateurs.
    • Résumé : Étude des difficultés qui surgissent dès lors que l’on essaye d’atteindre un haut niveau de fiabilité pour un grand nombre d’utilisateurs, et introduction à certaines des techniques utilisés par les Site Reliability Engineers (SRE) pour résoudre ces problèmes à Google.

      Bio : Gabriel Kerneis est ingénieur logiciel à Google Paris depuis 2014, dans l’équipe de l’Institut Culturel. Ancien élève de Télécom ParisTech et de l’ENS Cachan, il a précédemment effectué un doctorat d’informatique à l’université Paris Diderot et travaillé deux ans comme chercheur post-doctoral à l’université de Cambridge.

    • Année 2016-2017 :
      • 11 avril 2017. Jean-François Marckert. Des algorithmes de navigation dans le plan (travail en commun avec Nicolas Bonichon).
      • Résumé : Un algorithme de navigation sur un ensemble de points consiste en la donnée d’une règle pour choisir successivement « les points étapes » sur lesquels se déplacer, de manière à progresser vers un point cible spécifié. Ici, nous nous intéressons à des algorithmes dans le plan, définis par des règles géométriques: par exemple, un marcheur décide d’aller de Lyon à Moscou en s’arrêtant dans toutes les auberges qui ne sont « pas trop loin » de sa route (chaque notion de « pas trop loin », correspond à un algorithme de navigation). Bien sûr cela créé de nombreux détours, et chaque détour modifie potentiellement sa route ultérieure.

        Dans ce travail, on suppose que les points étapes sont répartis aléatoirement dans le plan selon un modèle appelé processus de Poisson ponctuel. On étudie pour différents algorithmes de navigation, la distance effectuée par le voyageur, et le nombre d’étapes. On discutera également ce qu’il peut se passer dans le pire des cas.

      • 28 mars 2017. Rémi Gribonval. Parcimonie et problèmes inverses.
      • Résumé : Supprimer le flou sur une image, restaurer un enregistrement sonore saturé, localiser l’épicentre d’un tremblement de terre à l’aide de sismomètres, reconstruire une image médicale 3D à partir de coupes 2D telles que des radiographies… Ces situations à première vue très différentes font en fait partie de la grande famille des problèmes inverses.

        L’intuition nous suggère à juste titre que de tels problèmes sont difficiles, voir insolubles dès que le nombre de variables inconnues excède celui des variables observées. Et pourtant des progrès considérables et des solutions efficaces ont été obtenus ces quinze dernières années en s’appuyant sur la notion de parcimonie. Objectif naturel pour la compression de données (MP3, JPEG), la parcimonie s’est ainsi révélée une propriété fructueuse là où on ne l’attendait sans doute pas.

        L’exposé dressera un panorama des principes et multiples facettes des approches exploitant la notion de parcimonie, dont on évoquera quelques-uns des avatars récents prometteurs.

      • 14 mars 2017. Lionel Morel. Les langages synchrones dans tous leurs états.
      • Résumé : Un avion ne se programme certainement pas comme un éditeur de texte… et heureusement. Dans cet exposé, nous reviendrons sur une success story française, celle des langages synchrones qui sont utilisés pour programmer de nombreux de systèmes de contrôle-commande critiques dans les avions, les trains, les centrales nucléaires. Nous parlerons de leur genèse, de leur sémantique de leur compilation. Nous nous attarderons en particulier sur Lustre, un langage flot-de-données. Nous terminerons par une petite ouverture vers d’autres langages flots de données non synchrones.

      • 28 février 2017. Maxime Amblard (sa présentation) et Maria Boritchev (sa présentation).
        Grande L3 deviendra mini-chercheuse, suivi de : Modélisation sémantique de la langue, une mise en pratique.
      • Changement de salle: amphi Schrödinger.

        Résumé : La langue est un vecteur de communication très efficace que chaque être humain utilise.
        C’est à la fois un moyen de transmettre des informations, mais aussi de construire notre
        pensée. Une multitude d’applications numériques que nous mobilisons quotidiennement,
        utilisent le traitement automatique de la langue.
        L’exposé débutera par la présentation d’un parcours d’étudiante du DI, de son stage de
        L3 à son stage de recherche de master. Le rapport des gens à leur·s pensée·s servira
        de fil conducteur pour arriver à la question de comment les gens pensent ?
        Pour apporter une réponse nous reviendrons à la fois sur la modélisation logique de la
        langue et présenterons un projet qui tente de lier ces représentations produites à partir
        du lambda calcul au fonctionnement cognitif.

      • 14 février 2017. François Pachet. Changement de salle: amphi SVT.
      • 7 février 2017. Yann Ollivier. Intelligence artificielle et raisonnement inductif : de la théorie de
        l’information aux réseaux de neurones.
      • Résumé : Les problèmes de raisonnement inductif ou d’extrapolation comme « deviner
        la suite d’une série de nombres », ou plus généralement, « comprendre la
        structure cachée dans des observations », sont fondamentaux si l’on veut
        un jour construire une intelligence artificielle. On a parfois
        l’impression que ces problèmes ne sont pas mathématiquement bien définis.
        Or il existe une théorie mathématique rigoureuse du raisonnement inductif
        et de l’extrapolation, basée sur la théorie de l’information. Cette
        théorie est très élégante, mais difficile à appliquer.

        En pratique aujourd’hui, ce sont les réseaux de neurones qui donnent les
        meilleurs résultats sur toute une série de problèmes concrets d’induction
        et d’apprentissage (vision, reconnaissance de la parole, récemment le jeu
        de Go ou les voitures sans pilote…) Je ferai le point sur quelques-uns
        des principes mathématiques sous-jacents et sur leur lien avec la théorie
        de l’information.

      • 31 janvier 2017. Jules Villard (Facebook) : Infer: Program Analysis at Facebook Speed and Scale.
      • Résumé : Static analysis improves software quality and saves time by catching bugs early
        in the development process. Infer is an open-source static analysis tool for
        Java, C, C++, and Objective-C.

        Infer is based on a compositional, interprocedural analysis able to
        automatically uncover deep issues, eg dereferencing null where both the null
        value and the dereference instruction come from multiple nestings of procedure
        calls. Compositionality is key to scaling to codebases that are not only large
        in size (eg, millions of lines of code), but also that evolve at a very high
        pace (eg, thousands of commits per week). I will detail how Infer’s analysers
        are designed around a reactive, compositional analysis scheduler. In particular,
        I will briefly demonstrate Infer’s main analysis, based on separation logic and
        biabduction, that allows to find memory safety violations.

        Infer is deployed at Facebook and analyses the Facebook app for Android and iOS,
        Facebook Messenger, Instagram, WhatsApp, and more. Each month, hundreds of
        potential bugs identified by Infer are fixed by our developers before they are
        committed to our codebases and deployed to people’s phones. I will show how
        Infer provides value for developers by seemlessly integrating into their
        workflow.

      • 17 janvier 2017. Laurence Danlos. (séminaire annulé).
      • 22 29 novembre 2016 en amphi J (attention au changement de date et de salle). Charlotte Truchet. Using Abstract Intepretation Techniques in Constraint Programming
      • Résumé : Constraint Programming (CP) is a domain of Artificial Intelligence that offers a variety of tools to model and solve hard combinatorial problems. Abstract Interpretation (AI) is a domain of Semantics that studies approximations of program traces in order to prove correctness properties. Although they are distinct scientific areas, these two domains have a lot in common. In both cases, we are interested in some set that is hard to compute or intractable: solution set in CP, concrete domain in AI. In both cases, instead of computing this set, we study some over-approximations of it: abstract domains in AI, consistent domains in CP. But the methods differ when the over-approximations are not good enough. CP has developed sophisticated algorithmic mechanisms to exactly solve the problem if the variables are discrete, or reach a given precision if they are continuous. In AI, the abstract domains themselves are refined, either by adding operators, or by increasing their expressivity. In the end, CP provides with solving methods that are very efficient on many NP problems, but are rather monolithic. For instance, they are unable to solve mixed problems with integer and real variables. AI analyzes huge programs using a lot of expressive abstract domains, but does not feature a notion of precision. In this talk, I will present some contributions at the intersection of CP and AI. I will show how to introduce the notion of abstract domain into CP, with the example of the Octagons which offer a good trade between efficiency and expressivity I will then present Absolute, a constraint solver without constraints: it is built upon a library of abstract domains called Apron.

      • 15 novembre 2016. Damien Pous. Du théorème des quatre couleurs à l’isomorphisme de Curry-Howard.
      • Résumé : Le théorème des quatre couleurs a un statut très particulier: ses seules preuves (re)connues nécessitent l’usage d’un ordinateur. Pour croire en ce théorème, il faut donc faire confiance non seulement aux humains qui l’ont écrite ou relue, mais aussi à une machine. J’expliquerai dans cet exposé comment l’assistant de preuve Coq permet de progresser sur cette point: c’est un logiciel permettant de formaliser et vérifier des preuves et des programmes. Je ferai en particulier une courte visite guidée de cet outil et de son fondement logique, l’isomorphisme de Curry-Howard.

      • 18 octobre 2016. Antoine Joux. Technical history of discrete logarithms in small characteristic finite fields.
      • Résumé : Due to its use in cryptographic protocols such as the Diffie–Hellman key exchange, the discrete logarithm problem attracted a considerable amount of attention in the past 40 years. In this talk, we summarize the key technical ideas and their evolution for the case of discrete logarithms in small characteristic finite fields. This road leads from the original belief that this problem was hard enough for cryptographic purpose to the current state of the art where the algorithms are so efficient and practical that the problem can no longer be considered for cryptographic use.

      • 4 octobre 2016. Patrick Loiseau. Game theory and learning for security.
      • *** changement de salle : amphi L! ***
        Résumé : Many situations in security can be modeled as a game between an attacker and a defender choosing their attack/defense strategies. Then, solving fundamental game theory problems can help build better defenses. We illustrate this through two examples. The first is allocation of security resources (e.g., in road control or airport security checks) where both players choose how to position their finite attack/defense resources. This problem relates to the famous Blotto games introduced by Borel in 1921 but still resolved only in a few special cases. The second example is attack detection where the attacker chooses an attack pattern and the defender chooses a classification algorithm to distinguish it from normal usage (non-attack). This problem touches upon the key question of how to do machine learning when the data is not ‘iid’ but rather generated by a strategic agent whose objective depends on the algorithm’s outcome. In both example, we give a few elements of solution and a brief overview of the range of open problems.

      • 20 septembre 2016. Emmanuel Jeandel. Pavages apériodiques du plan.
      • Résumé : Les pavages par tuiles de Wang ont été introduits dans les années 60
        pour apporter des réponses géométriques à des problèmes de logique.
        Une tuile de Wang est un carré dont les bords sont colorés. Etant
        donné un ensemble fini de tuiles de Wang, on cherche à savoir s’il est
        possible de paver le plan discret tout entier avec ces tuiles, en
        mettant une tuile par case de sorte que deux tuiles adjacentes aient
        la même couleur sur le bord qu’elles partagent. On s’intéresse plus
        particulièrement aux jeux de tuiles apériodiques, ceux pour lesquels
        un pavage existe, mais où il est impossible de paver le plan.
        périodiquement. Ces jeux de tuiles sont une des briques de base de la
        majorité des résultats de la théorie des pavages.

        Dans cet exposé nous présenterons les bases de la théorie des pavages,
        et comment construire un pavage apériodique en utilisant la théorie
        des automates.

       

    • Année 2015-2016 :
      • 12 avril 2016. Olivier Chapuis. Interaction Homme-Machine : une introduction et un panorama.
      • Résumé : L’Interaction Homme-Machine est la discipline qui se consacre à la conception, l’évaluation et la mise en œuvre de systèmes informatiques interactifs pour l’usage humain ainsi qu’à l’étude des phénomènes majeurs qui les entourent [Hewett et al]. Dans cet exposé on commencera par présenter les fondements de l’Interaction Homme-Machine: interface vs. interaction, systèmes interactifs, styles d’interaction, méthodes de conception et d’évaluation, ergonomie et approche expérimentale. Puis, on présentera des travaux récents sur le pointage (par exemple, acquisition de cible à la souris) et les très grands écrans à très hautes résolutions.

      • 29 mars 2016. Urtzi Ayesta. Design of communication networks: the role of mathematical modeling.
      • Résumé : We will explore the role of simple mathematical models in understanding and designing protocols for communication networks. A well-known citation says that all models are wrong, but that some can be useful. In this line of thought, we will show that mathematical models, despite not capturing all details of the physical world, can yield invaluable insights into how to design real networks. To illustrate the usefulness of mathematical models we will go through various toy examples in wireless networks, congestion control on the Internet, and Braess’s paradox.

      • 15 mars 2016. Maureen Clerc. Interfaces cerveau machine : état des lieux.
      • Résumé : L’interprétation en temps réel de l’activité cérébrale ouvre de nouvelles voies de communication et d’interaction entre l’humain et les machines. Cet exposé fera le point sur les possibilités effectives d’enregistrement, d’interprétation des données, de communication et d’interaction.

      • 9 février 2016. Nicolas Schabanel : Des molécules qui calculent et assemblent des formes.
      • Résumé : Cet exposé sera une présentation de nouveaux modèles de calcul qui sont effectivement implémentés en laboratoire dans des bechers par… des molécules. Ces calculs sont obtenus par exemple laissant des molécules artificielles à base d’ADN se replier sous forme de tuiles de taille nanoscopique, puis s’assembler par affinités pour réaliser des formes géométriques arbitraires de quelques centaines de nanomètres de diamètre. Le premier modèle effectif remonte à la thèse d’Erik Winfree en 1998 qui proposa le modèle d’auto-assemblage algorithme dont il démontra qu’il peut implémenter n’importe quel calcul Turing. Les premières étapes de son modèle furent ensuite réalisées en becher à l’aide de molécules d’ADN par Paul Rothemund qui obtint en 2001 une implémentation des triangles de Sierpinski. Depuis, différentes variantes ont été proposées aussi bien du côté des modèles théoriques, que des implémentations expérimentales. Ceux-ci ont permis la réalisation de smileys, cartes, alphabets, un compteur binaire (Evans, 2014)… nanoscopiques ainsi que tout récemment les prémices d’une robotique nanoscopique à base d’ADN, donc potentiellement compatible avec la vie. Dans cet exposé, nous présenterons une introduction à ce nouveau type de calcul par nature interdisciplinaire qui sera… qui sait… peut-être le futur post-silicium de nos ordinateurs !

      • 2 février 2016. Angela Bonifati: Big Data Integration: from relational to graphs and optimisations.
      • Résumé : Data integration has been a long standing research challenge in the database community. However, the available solutions cannot be readily exploited in the presence of massive heterogeneous and/or user-defined datasets of the Big Data era. A key process in data integration is data exchange, which is the problem of translating data structured under a source schema according to a target schema and a set of source-to-target constraints known as schema mappings. We will present our contributions on the following problems: (i) graph data exchange with target constraints; (ii) schema mapping optimisation through the study of schema mapping equivalence and logical entailment.

        The above contributions led us to (i) investigate the problem of data exchange from relations to graphs in the presence of target constraints and to study the classical data exchange problems, namely the existence of solutions and query answering, by showing that they are intractable; (ii) to solve the equivalence and logical implication for more expressive (fragments of second-order) schema mappings, showing that both problems belong to NP. We conclude by presenting our work in progress and pinpointing a number of interesting open problems in big data integration scenarios.

      • 26 janvier 2016. Eric Colin de Verdière:Graphes sur les surfaces : algorithmique et topologie.
      • Résumé : Un graphe planaire est un graphe que l’on peut dessiner sans croisement dans le plan. Plus généralement, tout graphe peut être dessiné sans croisement sur une surface, si celle-ci est «suffisamment compliquée» (par exemple, le graphe complet à 7 sommets n’est pas planaire mais peut être dessiné sur la surface d’une bouée).

        L’exposé porte sur le mariage entre algorithmique et topologie pour les graphes sur les surfaces, et illustrera ses deux facettes :

        – les graphes sur les surfaces apparaissent dans un certain nombre d’applications en informatique (en infographie par exemple). Dans ce contexte, il est utile d’avoir des algorithmes efficaces pour réaliser des opérations topologiques naturelles. Par exemple, étant donnée une surface, comment la découper le long d’un graphe le plus court possible pour la rendre planaire (homéomorphe à un disque) ? L’algorithmique fournit ainsi un nouveau point de vue pour les questions de topologie ;

        – en algorithmique des graphes, certains problèmes difficiles (NP-durs) deviennent abordables si l’on se restreint à certaines classes de graphes, par exemple les graphes planaires ou les graphes dessinables sur une surface donnée. Dans ce contexte, la topologie vient servir d’outil à l’algorithmique.

      • 15 décembre 2015. Alin Bostan. Compter les excursions sur un échiquier.
      • Résumé : Imaginons un échiquier s’étendant à l’infini dans les directions Est et Nord, et supposons qu’un « roi biaisé » puisse se déplacer d’une case vers l’Est, l’Ouest, le Sud-Ouest ou le Nord-Est. Si ce roi part du coin inférieur gauche de l’échiquier, combien existe-t-il d’excursions, c’est-à-dire de chemins possibles qui le font revenir à son point de départ en un nombre fixé de pas ? En 2001, Ira Gessel, mathématicien de l’Université Brandeis aux États-Unis, conjectura une belle formule pour ce nombre de possibilités. Depuis l’énoncé de cette conjecture jusqu’à sa première preuve en 2008, qui utilisait de façon cruciale la puissance des ordinateurs, puis sa première démonstration purement humaine en 2013, beaucoup de mathématiciens se sont confrontés à ce problème par des approches très différentes. Dans cet exposé nous allons placer le problème dans un contexte plus large -le dénombrement de chemins confinés dans un cône-, le motiverons, et survolerons quelques résultats récents. En particulier, nous nous concentrerons sur la classification des marches à petits pas dans le quart de plan. Dans ce cadre, nous verrons que la suite des nombres des excursions vérifie une récurrence linéaire si et seulement si un certain groupe, associé à l’ensemble de pas autorisés, est fini.

      • 24 novembre 2015. Jérémie Dequidt. Simulation médicale interactive : principes et applications
      • Résumé : La simulation bio-mécanique, utilisée pour des applications médicales, repose sur une approche multi-disciplinaire (informatique, robotique / automatique, mathématiques appliquées). L’objectif de cet exposé est de présenter la chaîne de traitements qui permet de passer d’images médicales de patient à un patient virtuel _opérable_ et d’en détailler les différents enjeux scientifiques. En particulier, nous évoquerons les aspects de modélisation géométriques, les modèles (bio-)mécaniques basés sur les éléments finis, la gestion des interactions (contacts, retour d’efforts…) et les optimisations nécessaires (solveurs, parallélisation, desynchronisation…) pour que la simulation soit interactive tout en étant réaliste.

        La plate-forme de simulation open source SOFA sera présentée ainsi que plusieurs applications de simulation médicale: simulateurs d’entraînements, application de planification et applications de guidage per-opératoire en utilisant la réalité augmentée.

      • 10 novembre 2015. Gabriel Kerneis (Google Cultural Institute). Infrastructure for culture: the life of a software engineer at the Google Cultural Institute.
      • Abstract : The Google Cultural Institute develops « technologies to make the world’s culture accessible ». In this talk, we will take a behind-the-scene look at what that means from a backend software engineer perspective. We will study several tools used on a daily basis at Google to solve some hard (and, sometimes, even harder) problems, ranging from algorithmic challenges such as classifying millions of artworks, to production issues such as getting your job scheduled on the the right cluster.

        Bio: Gabriel Kerneis never really knew what he wanted to do. He started with a master of engineering at Télécom ParisTech, and a master of science at ENS Cachan. Research looked exciting, so he did a PhD in Computer Science at Université Paris Diderot, focusing on program transformations for lightweight concurrency in C. Then, he spent two years at the University of Cambridge as a post-doctoral research associate, formalizing the instruction set architecture of Power micro-processors. But he finally came back to Paris and industry to work as a software engineer at the Google Cultural Institute.

      • 3 novembre 2015. Oliver Sinnen. Object Oriented parallelisation with Java.
      • Abstract: Doubts about the omnipresence of parallel computing should have vanished when quad-core (!) mobile phones came out a couple of years ago. So we have to deal with parallel programming on all computing devices, including desktop PCs, tablets, mobile phones and smart watches. Most applications in this area, however, are not very amicable to parallelisation as they are Object Oriented (OO) programs with a Graphical User Interface (GUI). This is in stark contrast to the programs and computation tasks typically found in traditional parallel and high performance computing. So this talk will discuss some of the parallelisation and concurrency challenges we face in this Object Oriented parallelisation area. We focus here on Java as an example for a widely used Object Oriented language — a language that is also used on mobile platforms (Android). Two approaches, following different philosophies, are studied: (1) Using a traditional approach to shared-memory parallel programming, namely OpenMP, in the new OO context, called Pyjama. (2) A modern task-based approach to parallelisation achieved with a few simple annotations (or keywords) in a Java program, called Parallel Task. Both technologies are for OO languages and go beyond classical parallel computing by considering GUIs and uncertainty about the target parallel system. These technologies were developed in the Parallel and Reconfigurable Computing group of the University of Auckland (www.parallelit.org).

      • 20 octobre 2015. Frédérique Bassino. Automates finis : énumération et analyse.
      • Résumé : Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l’ensemble respectivement des états initiaux et des états terminaux). Les automates (resp. minimaux) constituent une représentation (resp. canonique) des langages rationnels et de ce fait jouent un rôle important en informatique.

        On présentera des résultats concernant l’énumération des automates déterministes et accessibles, ie dans lesquels tout état peut-être atteint par un chemin partant de l’unique état initial. On déterminera ensuite précisément la proportion asymptotique d’automates minimaux parmi les automates déterministes accessibles et complets.

        Ces estimations sont obtenues en grande partie grâce à une interprétation combinatoire des propriétés structurelles des automates et à des bijections qui permettent de se ramener à l’étude combinatoire de tableaux particuliers.

        Ces résultats ont des conséquences importantes en terme de complexité en moyenne d’algorithmes manipulant des automates (algorithmes de minimisation de Moore et Hopcroft, génération aléatoire d’automates).

        Cet exposé s’appuie sur des travaux communs avec Julien David, Cyril Nicaud et Andrea Sportiello.

      • 22 septembre 2015. Philippe Xu (Université de Technologie de Compiègne). Voitures autonomes : où en sommes-nous ?
      • Résumé : Depuis l’apparition de la très médiatique « Google Car », de nombreux constructeurs automobiles promettent l’arrivée des voitures totalement autonomes dans les dix prochaines années. Où en sommes-nous réellement et quels sont les défis restant à relever ? Dans cet exposé, nous présenterons tout d’abord l’évolution de l’intelligence artificielle en robotique depuis ses débuts au milieu du 20ème siècle. Puis nous nous focaliserons sur le cas des véhicules autonomes. En particulier, nous aborderons la compréhension de scènes routières sous la forme d’un problème de fusion d’informations. Enfin, nous présenterons différents axes de recherches couvrant notamment l’utilisation de cartes digitales et de communications entre véhicules et infrastructures routières.

    • Années précédentes :
      • 5 mai. Arnaud Durand: Dependence logic and team semantics : computational aspects.
      • Résumé : Dependence logic is an extension of first-order logic that allows to capture the concept of dependence that arose in many area of computer science, mathematics, physics and statistics. This formalism (and similar others introduced recently) is defined using the notion of team semantics, a generalization of the usual Tarskian semantics used for first-order logic. In this talk we will present the basics of dependence logic and related formalisms (their syntax, semantics and model-theoretic aspects through numerous examples). In particular, we will investigate their expressive power in terms of complexity classes that can be captured (from P to PSPACE).

      • 21 avril. Paola Goatin: Lois de conservation pour la modélisation du trafic routier et piétonnier.
      • Résumé : La modélisation du trafic routier et des mouvements de foule peut se faire à différentes échelles: on peut distinguer entre des approches microscopiques, mésoscopiques et macroscopiques. Dans cet exposé, je me concentrerai sur les modèles macroscopiques, qui consistent en des (systèmes de) lois de conservation dérivées de la dynamiques des fluides. Ces équations aux dérivées partielles décrivent l’évolution spatio-temporelle de grandeurs macroscopiques telles que la densité de voitures ou de piétons et leur vitesse moyenne. Je détaillerai quelques modèles, et je montrerai des applications à la prévision et au contrôle optimal du trafic.

      • 7 avril. Marie-Paule Cani: Modélisation 3D Expressive : Façonner les éléments d’un monde virtuel.
      • Résumé : Malgré nos nombreux moyens d’expression, il nous est difficile de communiquer directement des formes tridimensionnelles imaginaires : ces dernières doivent être dessinées ou sculptées sur un matériau servant de support. L’interaction visuelle qui en résulte permet au créateur de raffiner progressivement sa pensée et de passer d’une ébauche grossière au modèle final. Offrir ce type de création progressive sur support numérique aurait de multiples avantages, comme par exemple le fait de pouvoir dessiner, mais en 3D, ou celui de pouvoir sculpter des formes statiques, mais aussi des formes en mouvement.

        Peut-on faire de l’outil numérique un support aussi facile à utiliser qu’un papier et un crayon, pour pouvoir librement ébaucher et raffiner des formes 3D? Cet exposé passe en revue une série d’avancées récentes dans ce domaine. Nous montrons d’abord que pour permettre une telle modélisation « expressive », les modèles 3D doivent être revisités dans une perspective centrée utilisateur, et en particulier incorporer des connaissances, pour réagir de la manière attendue aux gestes de design. Nous illustrons cette méthodologie dans trois cas d’utilisation : la création de nouvelles formes 3D à partir de croquis 2D, les opérations de transfert qui adaptent automatiquement les objets à un autre contexte, et la sculpture virtuelle qui permet de modifier progressivement des contenus complexes. Grâce à cette nouvelle génération de modèles, l’utilisateur peut interagir via des gestes intuitifs tout en s’appuyant sur l’outil numérique pour compléter automatiquement les détails ou pour maintenir un certain nombre de contraintes en matière de réalisme.

      • 24 février. Pas de Sieste cette semaine, mais une réunion d’information sur les échanges internationaux.
         

      • 10 février. Jean-Pierre Tillich: Codes LDPC.
      • Résumé : Les codes correcteurs d’erreurs sont une composante très importante pour beaucoup
        de transmissions numériques : elles permettent notamment de les rendre robustes
        vis à vis du bruit souvent inévitable qui se produit dans le canal de communication.
        En substance, elles consistent à prendre un message destiné à
        transiter sur un canal de communication et à le transformer en un message plus long
        avec des parties redondantes (c’est l’opération de codage).
        Ce message redondant est alors transmis sur le canal de manière à pouvoir retrouver le message initial
        même si des parties du message redondant se trouvent altérées. Cette deuxième opération est appelée le
        décodage.

        La théorie de Shannon a permis d’établir les limites ultimes en termes
        de débit de communication possible dans un tel cadre. Cette théorie montre même que des stratégies de codage
        aléatoire permettent en principe d’atteindre les limites en question. De telles stratégies
        ont néanmoins un coût prohibitif en termes de complexité de décodage.
        La théorie du codage a cherché (entre autres!) des manières de coder
        permettant à la fois de se rapprocher le plus possible de la limite de Shannon tout en ayant
        un décodage qui soit de faible complexité.

        Ces dernières années, une manière très populaire de réaliser cette opération de codage et de décodage
        à émergé. Elle apparait maintenant dans grand nombre de standards de communication et permet
        effectivement de fiabiliser les communications numériques dans des conditions très proches
        de la limite de Shannon avec des algorithmes de décodage de complexité quasi-linéaire.
        Elles consistent à faire en sorte que les messages transmis appartiennent à un
        espace vectoriel qui est donné par des équations linéaires très creuses : ce sont les codes LDPC
        comme « Low Density Parity Check ». Nous montrerons dans cet exposé en quoi le caractère creux
        des équations linéaires facilite grandement le décodage et donnerons des éléments de la théorie qui a
        permis cette avancée.

      • mercredi 4 février 2015 à 13h30. Fernando Pereira: Divergence analysis.
      • *** Attention, changement de date! ***  

        Abstract : The growing interest in graphics processing units has
        brought renewed attention to the Single Instruction Multiple Data
        (SIMD) execution model. SIMD machines give application developers
        tremendous computational power; however, programming them is still
        challenging. In particular, developers must deal with memory and
        control flow divergences. These phenomena stem from a condition that
        we call data divergence, which occurs whenever two processing elements
        (PEs) see the same variable name holding different values. This talk
        describes a static analysis to discover data divergences, which is the
        result of a long term cooperation between the Federal University of
        Minas Gerais, Brazil, and INRIA, Rennes. This analysis, currently
        deployed in an industrial quality compiler used by NVIDIA, is useful
        in several ways: it improves the translation of SIMD code to non-SIMD
        CPUs, it helps developers to manually improve their SIMD applications,
        and it also guides the automatic optimization of SIMD programs. We
        demonstrate this last point by introducing the notion of a divergence
        aware register allocator. This allocator uses information from our
        analysis to either rematerialize or share common data between PEs. As
        a testimony of its effectiveness, this register allocator has improved
        the execution time of standard CUDA benchmarks in over 25%.

      • mercredi 28 janvier 2015. Pas de Sieste cette semaine mais cours de Gérard Berry, professeur au collège de France.
      •  

      • 6 janvier 2015. Pierre-Etienne Moreau: Term rewriting and rule based programming in Java.
      •  

      • 9 décembre 2014. Stéphane Gaubert: L’approche opérateur des jeux avec paiement moyen : un tour d’horizon.
      • Le résumé.
         

      • 2 décembre 2014. Claude-Pierre Jeannerod: Analyse d’algorithmes en arithmétique virgule flottante.
      • Résumé : L’arithmétique virgule flottante est le moyen le plus couramment
        utilisé pour calculer avec des (approximations des) réels sur ordinateur. 
        Si cette arithmétique est par nature inexacte, la norme IEEE qui la régit
        définit un cadre strict dans lequel il est possible d’analyser et prédire de
        façon tout à fait rigoureuse le comportement de nombreux algorithmes 
        numériques de base (sommes, produits scalaires, arithmétique complexe, …).
        Dans cet exposé, nous illustrerons ce principe à l’aide de résultats obtenus 
        très récemment, qui revisitent une partie de l’analyse numérique classique.

      • 25 novembre 2014. Frédéric Prost (LIP): Vers la résolution du jeu d’échecs ?
      • Résumé : Le jeu d’échecs a souvent été présenté comme impossible à résoudre du fait de son énorme complexité. Le nombre de positions légales de ce jeu est compris entre 10^43 et 10^50 et le nombre de parties « intéressantes » possibles tourne autour de 10^120. Ces nombres sont à mettre en regard du nombre d’atomes de l’univers estimé à 10^79.

        Dans cet exposé je montrerais comment en utilisant une approche hybride humain/machine, on a pu résoudre avec très peu de moyens une variante du jeu d’échecs sur un échiquier 5×5. Pour cette variante le nombre de positions légales tourne autour de 10^20. Nous verrons ensuite comment cette approche peut permettre d’imaginer la résolution du jeu sur un échiquier 6×6, voire sur 8×8, dans un futur proche.

      • 4 novembre 2014. Aurélien Géron et Mathias Kende (Google): Understanding YouTube videos.
      •  

      • 21 octobre 2014. Marc Girault (Orange) : L’outil cryptographique.
      • Résumé : Nous commençons par présenter les trois buts principaux de la cryptographie (confidentialité, intégrité, authenticité) ainsi que les trois types d’algorithmes qui permettent de les atteindre (chiffrement, signature, authentification). Puis nous montrons à quel point la cryptographie est présente dans le monde numérique qui est le nôtre. Nous expliquons ensuite la différence entre cryptographies symétrique et asymétrique, avant d’évoquer les algorithmes phares de chacune d’entre elles : DES et AES d’un côté ; RSA et courbes elliptiques de l’autre. Pour finir, s’il nous reste quelques minutes, nous entrerons un peu plus dans le détail de ces dernières.

      • 16 septembre 2014. Erol Gelenbe :Consommation d’énergie et qualité de service en informatique.
      • Résumé : L’informatique et les télécoms consomment désormais près de 5% de l’électricité mondiale et ont un impact CO2 comparable à celui du transport aérien. L’augmentation annuelle de ces chiffres est de l’ordre de 7%. Que faire pour utiliser au mieux, sinon freiner, cette croissance? Cet exposé examinera sur une base scientifique ces évolutions et suggérera des pistes pour utiliser au mieux l’impact des TIC sur l’ensemble de la consommation d’énergie dans le monde.
        Erol Gelenbe est membre de l’Académie des Technologies et titulaire de la chaire « Dennis Gabor » à l’Imperial College, Londres.

      • 20 mai 2014. Xavier Allamigeon : Relations entre la complexité de la programmation linéaire et celle des jeux à paiement moyen.
      • Résumé : Dans cet exposé, je parlerai de résultats récents portant sur la relation entre deux problèmes ouverts : l’existence d’un algorithme fortement polynomial pour la programmation linéaire, et la résolution des jeux à paiement moyen en temps polynomial.
        Le lien entre ces deux problèmes est établi en transposant l’algorithme du simplexe à la programmation linéaire dite « tropicale », c’est-à-dire sur le semi-anneau max-plus. L’algorithme obtenu permet de transférer aux jeux des résultats de complexité sur la méthode du simplexe. J’expliquerai comment cela a permis de montrer que les jeux à paiement moyen peuvent être résolus en temps polynomial en moyenne.
        L’exposé repose sur plusieurs travaux menés en collaboration avec Pascal Benchimol, Stéphane Gaubert et Michael Joswig.

      • 22 avril 2014. Ha Duong Phan : Systèmes dynamiques discrets : sujets de recherches et applications.
      • Résumé : Beaucoup de systèmes complexes peuvent être représentés par des modèles discrets et leurs comportement peuvent êtrelations entre la complexité de la programmation linéaire et celle des jeux à paiement moyenre étudiés par le biais de structures algébrique et combinatoires. Dans cet exposé, je présente le modèle de Piles de sable (sous un autre nom : le Chip Firing Game) qui est le modèle de plusieurs systèmes dans l’informatique, les mathématiques, la physique ou l’économie; puis je parle de différentes méthodes pour étudier ce modèle, notamment en utilisant la structure de « sandpile group », de polynôme de Tutte et de matrice laplacienne.

      • 8 avril 2014. Nicolas Perrin: Aspects algorithmiques de la marche robotique.
      • Résumé : La marche a certains avantages sur les autres moyens de locomotion, mais elle est aussi probablement celui dont l’algorithmique associée est la plus complexe. La marche bipède, en particulier, est le plus complexe de tous les types de marches, et malgré des progrès continus depuis plus de 40 ans, elle demeure à ce jour un problème largement ouvert.
        J’expliquerai dans un premier temps comment certains aspects mécaniques de la marche ont eu une influence directe sur la conception des robots bipèdes ainsi que sur les algorithmes créés pour les faire marcher. Après cette introduction, je montrerai que le caractère hybride de la marche soulève des questions théoriques spécifiques dans les domaines de la commande, de l’optimisation et de la géométrie algorithmique. À cette occasion, je présenterai certains de mes travaux et collaborations dans les domaines de la commande prédictive pour la marche et de la planification de pas.

      • 25 février 2014. Jean Goubault-Larrecq. NetEntropy: de l’efficacité déraisonnable des statistiques en détection d’intrusions informatiques (travail en commun avec Julien Olivain).
      • Résumé : NetEntropy est un plugin du logiciel de détection d’intrusions Orchids,
        développé à INRIA et l’ENS Cachan. Son but est de détecter certaines attaques réseau, difficiles à caractériser, notamment parce qu’elles attaquent des protocoles chiffrés.

        Comme exemple, je considérerai l’attaque mod_ssl de 2003, qui est déjà un bijou d’ingénierie en soi. Je la décrirai en partie, pour que l’on puisse apprécier le niveau de sophistication que les attaquants sont prêts à atteindre aujourd’hui (et depuis plus de 10 ans).

        J’expliquerai ensuite comment NetEntropy la détecte. La question fondamentale est la suivante: étant donnée une suite de n octets, cette suite peut-elle être classifiée comme le préfixe d’une suite infinite aléatoire uniforme?

        Je montrerai que, d’une part, l’estimateur de Paninski, découvert en neurosciences en 2004, fournit une très bonne approximation de la valeur que devrait prendre l’entropie statistique si le flux était vraiment aléatoire uniforme. Mais surtout, les intervalles de confiance sont très petits, c’est-à-dire que la précision de l’estimation est très grande—d’une façon qui défie l’intuition. Je montrerai notamment que NetEntropy détecte des flux non uniformes avec très forte confiance après seulement quelques dizaines d’octets. C’est beaucoup moins que les 256 octets différents qui existent! Et tout ceci est prouvé: la clé du miracle est un théorème de 2000 dû à Moddemeijer, que j’énoncerai.

      • 18 février 2014. Olivier Teytaud: Optimisation et systèmes électriques.
      • Résumé : Qu’est-ce-que l’optimisation dynamique stochastique ? L’optimisation non-linéaire est la recherche de x tel que f(x) soit minimal. f étant la donnée du problème, supposée accessible comme oracle. L’optimisation est dite stochastique est le cas où f(x) est stochastique; en fait f(x)=Esperance g(x,w), où w est une variable aléatoire. L’oracle est alors stochastique.
        L’optimisation est dite dynamique d’horizon T lorsque f(x) est le résultat d’un système dynamique, itéré T fois, et dépendant de x à chaque itération; on a un certain état initial s_0, on définit par récurrence s_{t+1}=transition(s_t,x,w); g(x,w)=C(s_T) pour une certaine fonction C.

        L’optimisation dynamique stochastique est un problème atrocement difficile. Après un survol des classes de complexité en jeu, on se laissera effrayer par le cas de problèmes de génération électrique à l’échelle d’un continent sur des décennies. Les méthodologies de programmation dynamique stochastique, de contrôle par modèle prédictif, de recherche directe de politique, seront présentées dans un cadre aussi unifié que possible.

      • 11 février 2014. Loick Lhote. Modélisation des algorithmes de réduction de réseaux: cas de LLL.
      • Résumé : Intuitivement, un réseau est un ensemble de points régulièrement disposés dans l’espace. En pratique, les réseaux sont représentés par une base formée de vecteurs linéairement indépendants. Un réseau admet une infinité de bases et réduire un réseau consiste à construire une bonne base ayant des vecteurs assez courts et assez orthogonaux à partir d’une base quelconque. L’algorithme LLL, inventé en 1982 par Lenstra, Lenstra et Lovasz, est le premier algorithme de réduction de réseaux en temps polynomial. On peut aussi le voir comme une généralisation de l’algorithme d’Euclide en dimension supérieure.

        Le groupe de Caen, autours de Brigitte Vallée, a développé une méthode originale appelée analyse dynamique qui s’est avérée très efficace dans l’étude des algorithmes du PGCD. Cette méthode est basée à la fois sur les méthodes classiques d’analyses d’algorithmes et sur les systèmes dynamiques. Si le cas de la dimension 1 est maintenant bien compris (cas des algorithmes du PGCD), l’étude des algorithmes en dimension supérieure ne fait que commencer. Cependant, la dynamique des algorithmes de type LLL est trop complexe pour envisager une étude directe.

        Lors du séminaire, je montrerai comment des simplifications dans l’exécution de l’algorithme LLL peuvent conduire à des modèles simples qui permettent une analyse. Selon le degré de simplification, les modèles sont bien connus (système dynamique des tas de sable ou chip firing game) ou alors complètement ouverts à l’analyse. La modélisation de l’algorithme LLL implique aussi une modélisation des entrées de l’algorithme. Je présenterai plusieurs modèles issus d’applications en cryptologie.

      • 28 janvier 2014. Laure Gonnord. Les seuls problèmes intéressants sont les problèmes indécidables :
        application à la synthèse de preuve de terminaison de programmes.
      • Résumé : Le problème de la preuve de terminaison de programme est bien connu pour être, dans le cas général, un problème indécidable. Ce constat étant fait, on peut quand même essayer de ne pas jeter complétement le bébé avec l’eau du bain. Le choix qui est fait ici est d’essayer de traiter le cas général par des algorithmes _conservatifs_ : si l’algorithme répond oui, alors le programme termine, dans le cas contraire, on ne peut conclure.

        Pour le cas qui nous intéresse, nous commençons par « prouver » que le programme termine en exhibant une fonction qui décroît à chaque transition et qui reste positive (fonction « de rang »). Pour ce
        faire, nous utilisons des algorithmes classiques en compilation et en analyse statique: compilation d’un programme vers un automate affine, calcul d’invariants polyédriques, et enfin nous adaptons un algorithme glouton de calcul d’un ordonnancement multidimensionnel pour calculer une fonction de ranking affine multidimensionnelle. J’exposerai ces techniques ainsi que l’algorithme final.

        Une fois la fonction de rang exhibée, nous sommes en mesure de calculer un effet de bord sympathique : une borne supérieure de la complexité pire cas du programme. 

        J’exposerai ensuite nos résultats expérimentaux et les pistes que nous explorons actuellement pour améliorer le passage à l’échelle, ainsi que quelques applications à d’autres domaines que la « simple » preuve de terminaison. 

      • 17 décembre 2013. Hugues Berry. La glie: l’autre moitié du cerveau, une approche de biologie computationnelle.
      • *** Ce séminaire aura lieu en amphi A. ***

        Résumé : Les cellules gliales sont des cellules non-neuronales qui constituent la moitié environ des cellules du cerveau humain. Récemment, l’idée a commencé à émerger que ces cellules pourraient moduler le traitement de l’information dans le cerveau, via un dialogue permanent avec les neurones. Mais les astrocytes, le sous-type principal de cellule gliale dans le cerveau, sont eux aussi interconnectés en réseaux et communiquent entre eux par la propagation d’ondes calciques. Même si de nombreux points sont encore sujets à controverse, l’image qui résulte de ces données récentes est celle de deux réseaux (celui des astrocytes et celui des neurones) partiellement interconnectés. Cependant, comme ces deux réseaux fonctionnent à des échelles de temps très différentes, leur étude expérimentale reste difficile et le recours à la modélisation peut permettre de comprendre un peu mieux ce système. Depuis quelques années, nous développons avec E. Ben Jacob (Université de Tel Aviv) un ensemble de modèles computationnels des réactions biochimiques qui sous-tendent la communication astrocyte-astrocyte et neurone-astrocyte. En particulier, je montrerai quelques uns de nos résultats récents concernant l’influence de la topologie des réseaux d’astrocytes sur la propagation des ondes calciques.

      • 26 novembre 2013. Jarkko Kari. Cellular automata classics. Le fichier pdf de sa présentation.
      • Résumé : Cellular automata are dynamical systems where a regular grid of identical cells evolves through synchronous updates on the cells using a local update rule. Cellular automata are used in physics to model various real world systems, in computer science to study massively parallel synchronous computation under realistic locality constraints, and in mathematics in the context of symbolic dynamics. We make a gentle introduction to the topic through classical examples. We explain basic concepts and cover fundamental results such as the Garden-of-Eden -theorem from the 1960’s.

      • 5 novembre 2013. Jacques Duparc Des automates alternants au mu-calcul en jouant des jeux.
      • Résumé : L’acceptation d’un mot par un automate non-déterministe revient à considérer
        un joueur qui aurait en charge le choix des transitions permises : ce mot est accepté lorsque
        ce joueur possède une stratégie qui conduise sa lecture en un état acceptant. Lorsqu’on ajoute un second
        joueur qui soit en concurrence avec le premier on obtient l’idée d’un automate alternant.
        L’acceptation d’un mot repose dès lors sur l’existence d’une « stratégie gagnante ».
        Pour de nombreuses logiques aussi, la satisfaction d’une formule repose également sur
        l’existence d’une « stratégie gagnante » dans un jeu bien défini.
        En partant de logiques rudimentaires, nous verrons comment s’articule cette « sémantique des jeux »
        afin de mieux comprendre le mu-calcul qui constitue une espèce de « méta-système formel » pour de
        nombreuses logiques utilisées en informatique et qui témoigne de liens forts avec la théorie des automates.
        Nous présenterons finalement le problème du « model-checking » du mu-calcul en temps polynomial,
        dont l’énoncé en terme de jeux est à la fois très naturel et très simple mais dont la résolution reste toujours ouverte.

      • 22 octobre 2013. Vadim Lyubashevski.
        Recent advances in cryptography: Being able to answer questions you don’t understand.
      • Résumé : The first construction of a fully-homomorphic encryption scheme in 2009 has arguably been the most exciting result in cryptography of the past decade. Such a scheme allows one to compute any function on encrypted inputs, which is analogous to giving correct answers to questions you don’t understand. In this talk, I will present the main ideas that go into constructing this primitive, and will give an almost complete description of one such scheme.

      • 1er octobre 2013. Pierre McKenzie. Peut-on comprimer la mémoire utilisée lors d’un calcul polynomial?

        *** Ce séminaire aura lieu en amphi J. ***
      • 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 (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, celle-ci ne permet toujours pas aujourd’hui de répondre à la question posée. Au passage, nous présenterons deux preuves de bornes inférieures, l’une inventée en 1966, l’autre faite en 2010, qui rencontrent étonnamment la même barrière quadratique. Si le temps le permet, 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.)