Séminaire du Département d'Informatique de l'ENS

Le séminaire rassemble des exposés généraux conçus pour être accessibles à tous : élèves/étudiants, doctorants, chercheurs.
Une participation régulière pendant la scolarité à ENS (environ 24 séminaires) peut permettre d’obtenir 3 ECTS pour le diplôme de l’ENS. L’élève/étudiant devra veiller que ses coordonnées soient bien inscrites sur la feuille de présence lors de chaque séminaire et demander la validation de ces ECTS lors de sa dernière année de scolarité.
La personnes responsable est Marc Pouzet .
Les exposés ont lieu au 45, rue d'Ulm, 75005 Paris, dans une salle à préciser au cas par cas.
La plupart des exposés sont filmés et consultables sur : http://savoirs.ens.fr/recherche.php?rechercheOption=&rechercheTerme=S%C3%A9minaire+g%C3%A9n%C3%A9ral+du+d%C3%A9partement+d%27informatique

2017-2018 Dates possibles séminaire du DI en alternance avec le seminaire du DMA : http://www.math.ens.fr/enseignement/seminaires.html

Mercredi 23 mai 2018 à 17h00

Mercredi 9 mai 2018 NB mardi 8 mai et jeudi 10 mai féries

Mercredi 25 avril 2018 Vacances de Printemps. Pas de séminaire.

Mercredi 28 mars 2018 à 17h00.

Mercredi 14 mars 2018 à 17h00.

Mercredi 31 janvier 2018. Semaine de césure ENS Ulm. Pas de séminaire

Mercredi 24 janvier 2018 à 17h00. pas de séminaire presentations cours DMA du 2e semestre;

Mercredi 10 janvier 2018 à 17h00. presentations cours DI du 2e semestre

Mercredi 13 décembre 2017 à 17h00.

Prochains exposés, 2017-2018

Mercredi 28 février 2018 à 17h30. "Lunar (Jérémy Bobbio)" and George Kadianakis (Tor project)

Peeling Onions at ENS

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5e.
NB. Ce séminaire aura lieu de 17h30 à 18h30.

Tor is a way to access the Internet securely and privately.
It's a way to escape the everyday surveillance that companies and governments have been imposing to people.
In this talk we are going to present Tor, as a software and as an organization, as well as give an overview of new features that have been in development lately.

Mercredi 11 avril 2018 à 17h00. Florence Maraninchi (Grenoble INP / Ensimag)

From Physical Timing Requirements to Certifiable Real-Time Systems: How to capture requirements and generate correct real-time programs?

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Working on various industrial case-studies in the past decade, we realized that, given the very quick evolution of hardware platforms, and the growing complexity of embedded software, it is, more than ever, necessary to start with a very general point of view.
On one hand we need to understand the physical timing constraints and tolerances as determined by control engineers for a given application (sampling frequencies and jitters, end-to-end latencies, etc.), without mentioning software entities like tasks or scheduling.
On the other hand we need to characterize precisely the computation and communication performances of a given execution platform, and assess their predictability.

Designing the implementation means finding space and time allocations for the application functional parts, in such a way that the physical constraints are met by construction, and in a provable way for certification authorities.
We will use examples with the Kalray MPPA, to illustrate the nature and specification of the timing constraints, the implementation schemes, and how the constraints can be met.

Exposés passés, 2017-2018

Mercredi 21 février 2018 à 17h00. Jean Krivine (IRIF)

Modeling biological "big mechanisms"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.
NB. Toutes nos excuses. Date pas optimale mais seule possibilité.

“Big mechanisms are large, explanatory models of complicated systems in which interactions have important causal effects. The collection of big data is increas- ingly automated, but the creation of big mechanisms remains a human endeavor made increasingly difficult by the fragmentation and distribution of knowledge. To the extent that the construction of big mechanisms can be automated, it could change how science is done”. Paul Cohen, DARPA 2014.

If biological big data has underlying “big mechanisms”, there is little hope that any mental construction can ever comprehend these “large explanatory models”. Moreover, because of the combinatorics of protein-protein interactions, no static map, database, or ontology list, can suffice to complement human brains in the design of these models. These simple observations have taken a large swath of molecular biologists away from any (formal or semi-formal) modeling activity. Most experimental biologists give little credit to existing models, which they know are partial, outdated and have little predictive power. Yet, while rejecting models, experimental biologists have to rely on implicit mental constructs in order to decide which experiment to set up. Thus every biologist has a model, either implicitly or explicitly. In this presentation, we argue that the lack of success story of formal models in Systems biology is not due to the impossibility of having accurate and useful models, but rather to the fact that one is confusing models of interactions with explanations of biological functions. Our approach is to view models as programs and biological functions as computations. If models are to be treated as programs what language one should use to assemble them is a critical point.

In this talk we will present the issue of modeling biological "big mechanisms": i.e, protein-protein interaction networks whose specification is too combinatorial to be explicitly represented. In particular we will discuss the lessons that can be learned from the DARPA "BIGMEC" project, in which we took part, and that involved conjuncts efforts from A.I experts, biologists and language theory computer scientists.

Mercredi 29 novembre 2017 à 17h00. Laurent Perron (Google)

"La Recherche Opérationnelle à Google" Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Dans cet exposé, nous présenterons les outils de Recherche Opérationnelle que nous avons développé à Google.
Ensuite, à travers quelques exemples, nous illustrerons les forces et les challenges que nous rencontrons quotidiennement.
Finalement, nous présenterons les dernières technologies et le changement radical qu'elles introduisent dans la résolution de ces problèmes difficiles.

Mercredi 25 octobre 2017 à 17h00.Louis Mandel (IBM Watson, NY)

"Prototyping a Query Compiler using Coq" Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Designing and prototyping new features is important in industrial projects. I will present our experience using the Coq proof assistant as a prototyping environment for building a query compiler for use in IBM's ODM Insights. I will discuss the pros and cons of using Coq for this purpose and describe our methodology for porting the compiler to Java for product integration.

The initial Coq prototype has evolved into Q*cert (https://querycert.github.io/), an open-source platform for the specification, verification, and implementation of query compilers. This platform includes support for SQL and OQL. It can generate code for execution on JavaScript, Spark and Cloudant. It internally relies on familiar database intermediate representations, notably the nested relational algebra and calculus. The platform also comes with a simple but functional and extensible query optimizers.

This is a joint work with Joshua Auerbach, Martin Hirzel, Avi Shinnar and Jérôme Siméon.

Pas d'exposés en 2016-2017

Exposés passés, 2015-2016

Mercredi 18 mai 2016 à 17h00. Sébastien Bubeck. (Theory Group, Microsoft Research, Redmond, USA)

"New Results at the Crossroads of Convexity, Learning and Information Theory"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

I will present three new results: (i) the Cramer transform of the uniform measure on a convex body is a universal self-concordant barrier; (ii) projected gradient descent with Gaussian noise allows to sample from a log-concave measure in polynomial time; and (iii) Thompson sampling combined with a multi-scale exploration solves the Bayesian convex bandit problem. The unifying theme in these results is the interplay between concepts from convex geometry, learning and information theory. No background in optimization will be assumed.

Video: http://savoirs.ens.fr/expose.php?id=2611

Mercredi 20 avril 2016 à 17h00.

" Pas de séminaire general mais un séminaire des doctorants"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Mercredi 13 avril 2016 à 17h00. Anne Canteaut (Inria)

"Chiffrer mieux pour chiffrer plus "

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé :
Les algorithmes de chiffrement, qui visent à protéger la confidentialité des données, se répartissent en deux grandes familles : les algorithmes symétriques, ou à clef secrète, qui nécessitent le partage d'un secret par les deux protagonistes, et les algorithmes à clef publique, comme le RSA, dans lesquels les clefs secrètes restent connues d'un seul acteur. Mais les algorithmes symétriques sont les seuls qui atteignent les débits de chiffrement requis par la plupart des applications et qui permettent une mise en oeuvre par des circuits de taille raisonnable. Les exigences d'implémentation extrêmement contraignantes sont donc un paramètre essentiel lorsque l'on veut concevoir un algorithme de chiffrement symétrique.

L'objectif de cet exposé est de décrire diverses techniques récentes de conception permettant de répondre à ces besoins. Nous verrons notamment que la conception de ces systèmes fait appel à la fois à des aspects très pratiques (coût d'implémentation...) et à des travaux à long terme de mathématiques discrètes.

[The slides will be in English, the talk will be in French.]

Video : http://savoirs.ens.fr/expose.php?id=2516

Mercredi 30 mars 2016 à 17h00. Remplacé par le séminaire de l'IHP.

Mercredi 16 mars 2016 à 17h00. Pascal Raymond. (Verimag)

"Analyse de pire temps d'exécution et programmation synchrone"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé :
Les systèmes embarqués sont des dispositifs informatisés dédiés à une tâche spécifique, typiquement le contrôle/commande d'un processus physique. On en trouve dans le domaine des transports (freinage assisté, allumage moteur, commande de vol), du contrôle de processus industriel, ou de la production d'énergie. Les termes de systèmes réactifs, systèmes temps-réel (dur) couvrent à peu près la même réalité.

Une caractéristique principale de ces systèmes est la criticité : les défaillances peuvent être catastrophiques. Il faut donc s'assurer de la correction de ses systèmes avant leur mises en service.

Pour être considéré comme correct, un tel système doit essentiellement : - calculer juste : il réalise bien la fonctionnalité attendue, sans bogue de conception ni erreur à l'exécution ; - calculer (suffisamment) vite : la vitesse de réaction du système doit être en adéquation avec la dynamique du processus physique qu'il contrôle.

L'approche synchrone, formalisée dans le courant des années 80, s'intéresse spécifiquement aux aspects fonctionnels. Elle propose un cadre idéalisé pour la conception des systèmes (concurrence déterministe), et fournit les outils nécessaires pour la programmation, la validation, la compilation et l'implantation du logiciel embarqué. L'outil Scade (Esterel technologies) est un exemple typique d'un environnement de programmation synchrone, utilisé en production dans l'industrie (commandes de vol Airbus et bien autres).

L'analyse temporelle cherche à vérifier que le temps de réaction du système implanté est conforme aux contraintes temps-réel de son environnement. Aux méthodes dynamiques classiques, basées sur le test et la mesure, se sont ajoutées à partir des années 90 des méthodes d'analyse statiques qui cherchent à déterminer des bornes supérieures garanties aux temps de réaction. Le problème de base de ces méthodes est l'estimation du pire temps d'exécution d'un code séquentiel donné sur une architecture donnée (Worst Case Execution Time, ou WCET).

Cet exposé présente les complémentarités des deux domaines, puis aborde plus spécifiquement des travaux récents qui visent à analyser la sémantique des programmes synchrones pour découvrir des chemins d'exécutions infaisables sur le code compilé, et donc, potentiellement, d'affiner les estimations de pire temps d'exécution.

Video : http://savoirs.ens.fr/expose.php?id=2458

Mercredi 2 mars à 17h00. Wendy E. Mackay. (Inria)

"Co-Adaptive Instruments. Can we reinvent the graphical user interface?"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

My research, in the field of Human-Computer Interaction, has the not-very-modest goal of reinventing how users interact with computers in general, and more specifically, the Graphical User Interface. The idea is to create less-brittle interactive systems that augment human capabilities and are actually worth learning over time. We build upon two concepts: Instrumental Interaction, which treats interaction as a first class object, and Co-Adaptation, which helps users to both learn (adapt to) the system and appropriate (adapt) it. We are particularly interested in the early phases of the creative design process––how to create a human-computer partnership that helps creative professionals express and explore their ideas. I will illustrate our work with a series of projects, many based on interactive paper with contemporay music composers at IRCAM in Paris.

Video: http://savoirs.ens.fr/expose.php?id=2431

Mercredi 17 février 2016 à 17h00. David Naccache (ENS)

"When Organized Crime Applies Academic Results: A Forensic Analysis of an In-Card Listening Device "

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

This paper describes the forensic analysis of what the authors believe to be the most sophisticated smart card fraud encountered to date. In 2010, Murdoch et al. described a man-inthe-middle attack against EMV cards and demonstrated the attack using a general purpose FPGA board, noting that “miniaturization is mostly a mechanical challenge, and well within the expertise of criminal gangs”. This indeed happened in 2011, when about 40 sophisticated card forgeries surfaced in the field. These forgeries are remarkable in that they embed two chips wired top-to-tail. The first chip is clipped from a genuine stolen card. The second chip plays the role of the man-in-the-middle and communicates directly with the point of sale (PoS? ) terminal. The entire assembly is embedded in the plastic body of yet another stolen card. The forensic analysis relied on X-ray chip imaging, side-channel analysis, protocol analysis, and microscopic optical inspections

Mercredi 13 janvier 2016 à 17h00. Bruno Pagano (Esterel technologies)

" Scade 6: Conception d'un langage de programmation synchrone et réalisation de son compilateur pour les systèmes embarqués critiques."

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé :
Dans le contexte des systèmes embarqués critiques, l'objectif principal du logiciel n'est pas d'effectuer des calculs extrêmement longs et complexes à partir d'une donnée qui lui est fournie initialement, mais de réagir de façon sure et déterministe aux évènements externes qui lui sont communiqués de manière régulière tout au long de son exécution. La réalisation de tels logiciels peut se faire en utilisant des langages de programmation dédiés dont la conception et les techniques de compilation sont un sujet de recherche actif depuis une trentaine d'années. Les langages de programmation synchrones, comme Esterel ou Lustre, ont prouvé leur utilité dans la réalisation des systèmes réactifs. Après une introduction aux principes des langages synchrones, cet exposé présentera à travers le langage de programmation Scade 6 (dialecte de Lustre) les travaux de recherche d'Esterel Technologies sur la réalisation et la compilation d'un langage textuel et graphique. Nous évoquerons les mécanismes particuliers à Scade qui ont été introduit ainsi qu'un travail en cours sur l'utilisation de Scade pour la simulation de systèmes physiques.

vidéo : http://savoirs.ens.fr/expose.php?id=2361

Mercredi 9 décembre 2015 à 17h00.

" Pas de séminaire general mais un séminaire des doctorants"

http://www.di.ens.fr/SeminaireDoctorants.html.fr#Mercredi_9_d_cembre_2015_17h00_2 Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Mercredi 25 novembre à 17h00. Nicholas Ayache (Inria).

" Le patient numérique personnalisé : images, informatique, médecine."

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Le patient numérique personnalisé est un ensemble de données numériques et d’algorithmes permettant de reproduire à diverses échelles la forme et la fonction dynamique des tissus et organes d’un patient singulier. C’est aussi le cadre unifié qui permet d’intégrer les informations provenant des images anatomiques et fonctionnelles du patient, ainsi que les informations qui décrivent l’histoire de sa maladie.

Le modèle numérique du patient personnalisé grâce à ses images permet d’assister le diagnostic en quantifiant l’information cliniquement utile, d’assister le pronostic en simulant l’évolution d’une pathologie, et d’assister la thérapie en planifiant, simulant et contrôlant une intervention. Voilà ce qui préfigure la médecine computationnelle de demain, une composante informatique de la médecine destinée à assister le médecin et au service du patient.

Mon exposé présentera les enjeux de la recherche actuelle dans ce domaine, et illustrera certains des algorithmes et des modèles mathématiques, biologiques et physico-chimiques mis en œuvre dans des contextes médicaux variés (neuroimagerie, oncologie, cardiologie interventionnelle, chirurgie digestive, etc.).

vidéo : http://savoirs.ens.fr/expose.php?id=2307

Mercredi 28 octobre à 17h00. Marie-Paule Cani (Grenoble INP)

"Towards Expressive 3D Modelling: New challenges in Computer Graphics"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Despite our great expressive skills, we humans lack an easy way of conveying the 3D shapes we imagine, even more so for dynamic shapes that change over time. Over centuries we relied on drawing and sculpture to convey shapes. However, these tools require significant expertise and time investment, especially when one aims to describe complex or dynamic shapes. With the advent of virtual environments one would expect digital modeling to replace these traditional tools. Unfortunately, conventional techniques in the area have failed, since even trained computer artists still create with traditional media and only use the computer to reproduce already designed content.
Could digital media be turned into a tool, even more expressive and simpler to use than a pen, to convey and refine both static and dynamic 3D shapes? This would make shape design directly possible in virtual form, from early drafting to progressive refinement and finalization of an idea. To this end, models for shape and motion need to be redefined from a user-centered perspective. This talk will present our recent work towards responsive shapes, namely high level models that take form, refine, move and deform based on user intent, expressed through intuitive interaction gestures.

Mercredi 14 octobre 2015 à 17h00. Jérôme FERET (INRIA & ENS)

"Réduction de modèles de voies de signalisation intracellulaire"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: :
Les voies de signalisation intracellulaire sont des cascades d'interaction entre protéines, qui permettent à la cellule de recevoir des signaux, de les propager jusqu'à son noyau, puis de les intégrer, ce qui, in fine, influe sur le comportement global de la cellule. Les protéines s'associent entre elles sur des sites de liaisons, puis modifient la structure spatiale de leurs voisines, ce qui a pour effet de cacher ou de découvrir leurs autres sites de liaisons, et donc d'empêcher ou de faciliter d'autres interactions. De vastes bases de données ont été conçues pour répertorier les différentes interactions connues entre les sites des protéines. Cependant, nous ne savons toujours pas clairement comment les propriétés physiologiques de la cellule émergent de ces interactions.

La difficulté principale est la grande combinatoire de ces modèles. En effet, chaque protéine a beaucoup de sites de liaisons. Ainsi, un très grand nombre de complexes biomoléculaires différents peut se former. Pour décrire ces modèles, nous proposons d'utiliser des graphes pour la représentation des complexes biomoléculaires et des règles de réécritures pour la spécification des interactions entre les protéines. En particulier, ces règles sont contextuelles : elles décrivent non seulement les transformations sur les complexes biomoléculaires, mais aussi les conditions nécessaires à ces transformations. Ceci offre une représentation très compacte et pratique d'un modèle. Par ailleurs ces règles permettent de formaliser le comportement des modèles à différents niveaux d'abstraction (qualitatifs ou quantitatifs). Malheureusement, l'écueil de la complexité combinatoire refait surface lorsque l'on cherche à calculer de manière effective ce comportement.

Nous proposons une méthode pour réduire la taille des systèmes différentiels qui décrivent le comportement de ces modèles. Nous utilisons une analyse du flot d'information entre les différents sites des complexes biomoléculaires. Ainsi, pour chaque site de liaison d'un complexe biomoléculaire, nous détectons quelles sont les parties de ce complexe qui peuvent influencer la capacité de lier ou de délier ce site. Nous en déduisons des paires de sites dont on peut abstraire la relation entre l'état de liaison, car les ensembles de sites qu'ils peuvent influencer sont disjoints. Cela nous permet de découper les espèces biomoléculaires en plus petits morceaux (en séparant de telles paires de sites). Nous obtenons ainsi un système différentiel portant sur la concentration de ces morceaux de complexes biomoléculaires, qui sont beaucoup moins nombreux que les complexes biomoléculaires du système différentiel du modèle initial, et ce sans jamais avoir écrit explicitement ce système initial. Pourtant, notre méthode de réduction est exacte : nous avons la preuve que la solution du système obtenu, est la projection exacte de la solution du système initial.

vidéo : http://savoirs.ens.fr/expose.php?id=2223

Mercredi 30 septembre 2015 à 17h00. Damien Stehlé (ENS Lyon)

"Manipuler les réseaux euclidiens"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: :
Un réseau est l’ensemble des combinaisons linéaires entières de vecteurs linéairement indépendants. Visuellement, le réseau forme une grille infinie de points régulièrement espacés. Les réseaux ont de nombreuses applications en informatique. Entre autres, ils apparaissent fréquemment en calcul formel, par exemple pour factoriser les polynômes à coefficients rationnels, et en cryptographie, aussi bien pour cryptanalyser que pour concevoir des protocoles. L’algorithme LLL, du nom de ses auteurs Arjen Lenstra, Hendriz Lenstra et László Lovász, permet de calculer une bonne représentation, ou base, d’un réseau donné. Cette représentation fournit de l’information intrinsèque sur le réseau manipulé. De nombreuses applications ont suivi la publication de l’algorithme LLL, et, du fait de ce succès, plusieurs accélérations algorithmiques ont par la suite été proposées. L’approche la plus efficace aujourd’hui repose, en interne, sur des calculs flottants en faible précision, donnant lieu à un algorithme hybride numérique-algébrique. Après avoir présenté les réseaux et quelques-unes de leurs applications, je décrirai l’approche hybride numérique-algébrique de l’algorithme LLL.
N.B. The slides will be in English, the talk will be in French.

video: http://savoirs.ens.fr/expose.php?id=2180

Exposés passés, 2014-2015

Vendredi 26 juin 2015 à 10h30. Vivek Sarkar (Rice University)

"Structured Parallel Programming Primitives and their use in Compilers, Runtimes and Debuggers for Parallel Systems "

Salle Jean Jaures, École normale supérieure, 29 rue d'Ulm, Paris 5ème.

In this talk, we claim that structured parallel programming greatly simplifies the task of writing correct and efficient parallel programs, while also capturing the flexibility of expressing asynchronous computations. We support this claim by introducing a family of structured parallel programming primitives developed in the Habanero Extreme Scale Software Research project at Rice University, and discussing semantic guarantees (e.g., deadlock freedom, data race freedom, determinism, serial elision) for different subsets of parallel programs that can be constructed with these primitives. We will then summarize results for compiler optimizations, runtime systems, datarace detection and repair for these subsets. If time permits, we will briefly discuss future directions for data-driven repair and synthesis of parallel programs in the new Pliny project.

video: http://savoirs.ens.fr/expose.php?id=2172

Mercredi 27 mai 2015 à 17h00. Jerome Pesenti (IBM Watson)

"Cognitive Computing"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Between IBM Watson's victory against Ken Jennings at Jeopardy, Google and Facebook's introduction of deep learning algorithms for speech and vision recognition in their consumer devices and applications, and the current hiring and buying binge around everything and everybody related to machine learning, there is an emerging feeling in the software industry that AI is finally on the brink of its big breakthrough: cognitive computing is about to change our every day lives. But the industry is facing new challenges. Developing software relying on natural language and machine learning requires a new methodology and new ways of gathering and treating data. It is more akin to scientific research than traditional engineering. I will describe the new advances in cognitive computing, show that there is substance behind the buzz, and explain the new challenges they bring to software engineering.

Video : http://savoirs.ens.fr/expose.php?id=2093

Mercredi 13 mai 2015 à 17h00. Serge Abiteboul (INRIA & ENS Cachan)

"Turning your digital self into a knowledge base"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

A Web user today has his/her data and information distributed in a number of services that operate in silos. Computer wizards already know how to control their personal data to some extent. It is now becoming possible for everyone to do the same, and there are many advantages to doing so. Everyone should now be in a position to manage his/her personal information. Furthermore, we will argue that we should move towards personal knowledge bases and discuss advantages to do so. We will mention recent works around a datalog dialect, namely Webdamlog.

video : http://savoirs.ens.fr/expose.php?id=2125

Mercredi 1er avril 2015 à 17h00. Laurent Viennot (INRIA)

"From spanners to distance oracles and compact routing"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

A classical area of research is devoted to compact data-structures in networks. Among all, the most prominent algorithmic problem of networks consists in routing. This basically consists in assigning some table at each node of a network and some label identifying each destination so that given his table and the label of the destination of a packet, a node can decide where to forward the packet. Many results of the domain concerns the trade-off between the quantity of information that is stored at each node and the quality of the routes this information provide. We will see that this problem is related to that of finding a spanner of the network that is a subgraph which approximates the original graph of the network with respect to distances: how many links can you remove from a graph without stretching too much distances ? This also leads to the problem of finding a compact distance oracle that is a data structure that approximates the distances inside a graph. The distributed version of the problem consists in assigning a small label to each node so that an estimation of the distance between two nodes can be computed from their two labels (without any auxiliary data-structure). Finally, we will see that this kind of techniques have recently been applied to road networks where distance labels offer an elegant solution for computing driving directions.

Video : http://savoirs.ens.fr/expose.php?id=2049

Mercredi 4 mars 2015 à 17h00. Nabil Mustafa (ESIEE)

Three discrete geometric structures and their applications

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Since the beginning of systematic research on geometric computing almost forty years ago, there has been a very fruitful interplay between the mathematical study of discrete geometric structures and the search for efficient solutions for a variety of problems involving geometric data.
In this talk I will illustrate this with three examples: well-separated pair decompositions (a property of point sets), separators (a property of geometric objects), and epsilon-nets (a property of the interaction of point-sets with geometric objects).

Video : http://savoirs.ens.fr/expose.php?id=2023

Mercredi 14 janvier 2015 à 17h00. Peter Marbach (University of Toronto)

Social Networks: A Research Vision and some Results

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Social network are very natural and familiar to us. Everyday, we use our social networks to interact with friends, co-workers, or members of our community. We use social networks for a variety of purposes be it for a friendly chat, getting advise on how to proceed with a project, or discussing what is happening in our community. Given that social networks are so familiar to us, and we use them so frequently in our everyday life, one would expect that we understand them very well. In particular, one would expect that we have a clear understanding of why we form social networks, how we form them, and how we use them. However, this does not seem to be the case. The question that we want to study whether it is possible to create a deeper and formal understanding of social networks by developing mathematical models that accurately describe why and how social networks are formed, and how we use social networks. As part of the talk, we will present results that provide some evidence that this might be indeed possible.

Video : http://savoirs.ens.fr/expose.php?id=1994

Mercredi 3 décembre 2014 à 17h00. Mathias Kende (Google)

"Understanding the Youtube videos"

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: YouTube has videos on almost any imaginable topic, but it remains a challenge for users to find the content they would like to see. One important step in organizing the YouTube content is to understand what the videos are about. We will present the work done in the Google Paris office on understanding and classifying video. See what we do to make sense of the hundred hours of video uploaded to YouTube each minute, as well as what we still need to improve.

Mercredi 19 novembre 2014 à 17h00. Vincent Danos (CNRS, ENS)

Approximations for stochastic graph rewriting

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: We present a method to compute approximate descriptions of a class of stochastic systems. For the method to apply, the system must be presented as a Markov chain on a state space consisting in graphs or graph-like objects, and jumps must be described by transformations which follow a finite set of local rules. The method is a form of static analysis and uses a technique which is reminiscent of theories of critical pairs in term rewriting systems. Its output is a system of coupled ordinary differential equations (ODE) which tracks the mean evolution of the number of (typically small) subgraphs. In some cases, these ODEs form an exact and finite description of these mean numbers. But even when the ODE description is only an approximation, it can often reveal interesting properties of the original system.

video : http://savoirs.ens.fr//expose.php?id=1894

Mercredi 1 octobre 2014 à 17h00. Jean-Michel Muller (ENS Lyon)

Rendre la virgule flottante plus rigoureuse

Salle Henri Cartan, 2e sous sol, Aile Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: L'arithmétique virgule flottante est de loin le moyen le plus utilisé pour représenter des nombres réels sur ordinateur. Elle souffre cependant d'une mauvaise réputation: on ne pourrait pas faire confiance aux résultats qu'elle retourne., A moins de faire de longs calculs d'erreur, qui eux mêmes sont d'ailleurs très approximatifs. Nous montrerons par quelques exemples simples qu'on peut obtenir des informations beaucoup plus précises qu'on ne le croit, que l'on peut prouver des propriétés d'algorithmes utilisant la virgule flottante, faire quand on en a besoin des calculs "exacts".

vidéo : http://savoirs.ens.fr/expose.php?id=1838

Exposés passés, 2013-2014

Jeudi 22 mai 2014 à 11h15. Jean-Paul Delahaye (Lille)

Comment définir et évaluer la complexité des objets numériques ?

Amphi Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: La théorie de la calculabilité propose une définition de la complexité des objets numériques : la complexité de Kolmogorov (introduite en 1965). Celle-ci est une mesure du «contenu incompressible d'information», mais ne doit pas être conçue comme une mesure de la «richesse en structures ou en organisation» (complexité structurelle), qui elle serait mathématiquement définie par la profondeur logique de Bennett (introduite en 1977). Les applications de la complexité de Kolmogorov (par le biais des algorithmes de compression de données) sont maintenant nombreuses : classification de textes et de musiques, évaluation de la ressemblance entre séquences génétiques, comparaison d'images, repérage du plagiat, identification des spam, détection des tentatives d'intrusion dans les systèmes informatiques, etc. L'évaluation de la complexité structurelle est plus difficile en pratique, mais des progrès ont été faits récemment qui permettent d'envisager des applications comme pour la complexité de Kolmogorov.

vidéo : http://savoirs.ens.fr/expose.php?id=1725

Lundi 28 avril 2014 à 11h00. Benoît Crabbé (Paris VII)

Construction à large couverture de la représentation du sens de phrases de langue naturelle.

Salle UV, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Dans cet exposé, je traiterai le problème de la construction à large couverture du sens de phrases de langues naturelles. Partant de l'hypothèse que la représentation du sens de phrases de langue naturelle s'appuie sur leur structure, la première partie de l'exposé présente un algorithme d'analyse syntaxique robuste à pondérations qui propose une désambiguisation des hypothèses d'analyse. La seconde partie de l'exposé présente un travail en cours destiné à illustrer le problème de la construction du sens par des représentations vectorielles en relation avec la conception d'un algorithme d'analyse syntaxique. Dans son ensemble l'exposé donnera ainsi une introduction à quelques problématiques traditionnelles du traitement automatique des langues naturelles : analyse syntaxique, apprentissage structuré et représentation compositionnelle du sens, situées dans le contexte de la recherche actuelle.

video : http://savoirs.ens.fr/expose.php?id=1706

Jeudi 13 mars 2014 à 11h15. Xavier Leroy (INRIA, Rocquencourt)

Comment faire confiance à un compilateur ?

Amphi Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé : Le logiciel critique - celui dont dépendent des vies humaines - nécessite des techniques de développement et de validation très particulières pour atteindre le niveau de fiabilité exigé. Parmi celles-ci on voit apparaître la vérification formelle du logiciel assistée par des outils (analyseurs statiques, prouveurs de programmes, etc). Cependant, la fiabilité de ces outils qui participent à la construction et la validation du logiciel est elle-même en question, menant à la conclusion que ces outils doivent eux-mêmes être formellement vérifiés. Je décrirai une avancée majeure dans cette direction: la preuve de correction, utilisant l'assistant de preuves Coq, du compilateur CompCert, un compilateur C réaliste et incluant un certain nombre d'optimisations.

video : http://savoirs.ens.fr/expose.php?id=1659

Jeudi 20 février 2014 à 11h15. Julia Lawall (INRIA, LIP 6)

A Foundation for Flow-Based Program Matching Using Temporal Logic and Model Checking

Amphi Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Coccinelle is a program matching and transformation tool for C code, founded on the notion of a semantic patch, in which matching and transformation specifications are expressed using a patch-like syntax. Coccinelle has been extensively used for bug finding and evolution in the context of the Linux kernel, and other C software. In this talk, we provide an overview of Coccinelle and its use on Linux code, as well as describing its internal design, based on a novel variant of the temporal logic CTL.
This is joint work with Julien Brunel, Damien Doligez, Rene Rydhof Hansen, and Gilles Muller

video : http://savoirs.ens.fr/expose.php?id=1603

Jeudi 30 janvier 2014 à 11h15. Stéphane Gaubert (INRIA et CMAP, École Polytechnique)

De la convexité tropicale aux jeux répétés

Amphi Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé : Une question aussi ancienne que la programmation linéaire consiste à trouver une règle de pivotage pour l'algorithme du simplexe conduisant à un nombre polynomial d'opérations. Une autre question consiste à trouver un algorithmerésolvant en temps polynomial un jeu répété déterministe dont la valeur est définie comme un paiement moyen par unité de temps. Sans résoudre aucune de ces deux questions, nous montrons qu'une réponse positive à la première entraînerait une réponse positive à la seconde, pourvu que la règle de pivotage satisfasse certaines conditions. La preuve de ce résultat fait appel à la convexité tropicale et nous servira de prétexte à faire une introduction à celle-ci. Cet exposé est basé sur un travail avec Akian et Guterman (arXiv:0912.2462, IJAC 2012) ainsi que sur un travail avec Allamigeon, Benchimol, et Joswig (arXiv:1308.0454, arXiv:1309.5925)

video : http://savoirs.ens.fr/expose.php?id=1591

Jeudi 5 décembre à 11h15. Benjamin Burton (University of Queensland, Australia)

Untangling knots using combinatorial optimisation

Amphi Rataud, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Unknot recognition is the algorithmic problem of determining whether a knot (i.e., a closed loop) in 3-dimensional space can be untangled. It is a major unsolved question as to whether this problem has a polynomial time solution. Here we present the first conclusive algorithm for unknot recognition which, although exponential time in theory, exhibits a clear polynomial time behaviour in exhaustive practical experiments. The algorithm marries together techniques from computational topology and combinatorial optimisation, and gives a glimpse of the rich potential that integer and linear programming have to offer in the world of 3-dimensional geometry and topology.

Video : http://savoirs.ens.fr/expose.php?id=1503

Lundi 18 novembre 11h15. Yann LeCun (Center for Data Science & Courant Institute of Mathematical Sciences, New York University)

Apprentissage Profond pour la Perception Automatique

Salle Henri Cartan, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Les tâches perceptuelles telles que la vision ou l'audition nécessitent la construction de bonnes représentations internes du monde perceptuel. Les méthodes classiques d'apprentissage automatique peuvent aisément construire des classifieurs à partir de données prétraitées, mais un des grands défis de l'intelligence artificielle est la découverte de méthodes permettant l'apprentissage automatiques de représentations internes à partir de données brutes.

Plusieurs résultats théoriques et empiriques suggèrent que le monde perceptuel se représente efficacement par une hiérarchie multi-niveaux dans laquelle les descripteurs sont de plus en plus globaux, invariants et abstraits à mesure qu'on progresse dans les niveaux. L'objectif des méthodes d'apprentissage profond est de permettre l'entrainement de telles architectures en combinant des données étiquetée et non-étiquetées.

Les réseaux convolutifs (ConvNets? ) sont un type particulier d'architecture profondes quelque peu inspirées par la biologie. Ils sont composés de plusieurs étages, contenant eux-mêmes une succession d'opérateurs tels que normalisation, banc de filtres, non-linéarités, et aggrégation spatiale. De telles architectures sont les détenteurs de records pour des tâches très diverses: reconnaissance d'objets dans les images, segmentation sémantique, segmentation d'images volumétriques, modélisation acoustique en reconnaissance de la parole, prédiction de réactivité chimique, reconnaissance de panneaux routiers, de caractères (latins et chinois), etc. Les derniers systèmes de reconnaissance de la parole et de l'image déployés par Google, IBM, Microsoft, Baidu, NEC et bien d'autres utilisent tous des architectures profondes, et la plupart utilisent des réseaux convolutifs.

Plusieurs méthodes supervisées et non supervisées pour l'entrainement de réseaux convolutifs seront présentées. Des applications seront présentées sous la forme de vidéos et de démonstrations en temps réel, en particulier un système de reconnaissance d'objets entrainable à la volée, un système d'étiquetage sémantique, et un détecteur d'objets. Une architecture matérielle spécialisée pour les réseaux convolutifs sera très brièvement décrite.

Lundi 30 septembre 11h15. Faith Ellen (University of Toronto)

Nonblocking Concurrent Data Structures

Salle Henri Cartan, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: A library of concurrent data structures can make the task of developing concurrent software much easier. Although sequential data structures can be transformed into concurrent data structures in straightforward ways using locks or transactional memory, the results are generally inefficient. We discuss some of the difficulties and techniques involved in constructing efficient concurrent data structures, including our recent work on balanced binary search trees.

Exposés passés, 2012-2013

Jeudi 6 juin 2013 à 11h15. Sampath Kannan (University of Pennsylvania)

Exponential Mechanism for Social Welfare - Private, Truthful, and Nearly Optimal

Amphi Rataud - École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Mechanism design is the problem of computing an optimal allocation of resources under criteria such as social welfare or revenue. The problem is more challenging than algorithm design because the inputs have to be elicited from selfish agents who may be able to derive an advantage by lying. A standard approach to overcome this challenge is to design incentive-compatible mechanisms where truth-telling is a dominant strategy or at least a Nash equilibrium. In this work we are concerned with another reason that strategic agents may lie - to protect the privacy of their data. This is a relatively new concern in the field of mechanism design. What is needed are mechanisms that are incentive-compatible and protect the privacy of data. We show that if the goal is social welfare then this is possible - nearly optimal social welfare can be achieved in general while protecting the privacy of the data. One the negative side, the exponential mechanism is not always computationally efficient. Efficiency has to be proved on a problem-by-problem basis.

Joint work with Zhiyi Huang

Video : http://savoirsenmultimedia.ens.fr/expose.php?id=1400

Lundi 10 juin 2013 à 10h00. Ramaswamy Govindarajan (Indian Institute of Science, Bangalore)

Compiling for Heterogeneous Multi-Core Architectures with GPUs

Salle S16 ( Aile Rataud, Niveau -1) - École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Rapid advancements in multi-core processor architectures along with low-cost, low-latency, high-bandwidth interconnects have made clusters of multi-core machines a common resource in today's world. Combined with this, the recent advances witnessed in Graphics Processing Units provide excellent opportunity for exploiting large amounts of parallelism. In this talk I will discuss exploiting different types of parallelism in heterogeneous accelerator-based multi-core architectures. In particular we present our work on compiling programs written in different languages (StreamIt? , MATLAB, and X10) for GPU-based architectures. We propose techniques to efficiently map applications for synergistic execution on CPU and GPU cores. We also propose novel techniques for automatic memory management to improve the ease of programming.

Jeudi 13 juin 2013 à 11h15. Mary Sheeran (Chalmers university of technology, Sweden)

Obsidian: generating GPU kernels from Haskell

Salle Dussane - École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Abstract: Obsidian is an embedded language (in Haskell) for implementing high performance kernels to be run on Graphics Processing Units (GPUs). Like in our earlier work on Lava for hardware description and generation, we would like to have our cake and eat it too. We want both to raise the level of abstraction at which the programmer works from that of CUDA (which we generate) and still to give the programmer fine control over low level details. We illustrate this by showing details of some kernel optimisations; we make use of two different array representations,which we call pull and push arrays. Obsidian also uses types to model the hierarchical nature of the GPU, to help the programmer to write suitable (and easy to compile) GPU programs. Benchmarks show that the low-level, detailed control offered to the programmer does have an associated pay-off in running time. We will discuss limitations of Obsidian, which is very much work in progress.

Joint work with Joel Svensson

Mardi 23 avril 2013 à 14h30. Aude Oliva (Computer Science and Artificial Intelligence Laboratory, MIT)

Predicting Image Memorability

Salle Dussane - École normale supérieure, 45 rue d'Ulm, Paris 5ème

Abstract: When glancing at a magazine or browsing the Internet, we are continuously exposed to images. Despite this overflow of visual information, humans are extremely good at remembering thousands of pictures along with their visual details. But not all images are created equal. Whereas some images stick in our minds, others are ignored or quickly forgotten. What makes an image memorable? Our recent work shows that one can predict image memorability, opening a new domain of investigation at the interface between human cognition and computer vision.

Ce séminaire est organisé avec le département d'études cognitives

Mardi 16 avril 2013 à 11h15. Claude Berrou (Telecom Bretagne)

Une théorie de l'information mentale

Salle Dussane, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé : 9 fois 8 : 72, notre numéro de sécurité sociale, les prénoms de nos amis, voilà ce qu’on peut appeler de la « pure information mentale », rangée « quelque part » dans notre cerveau pour être exploitée en cas de besoin. Chacune de ces informations, nous pouvons la rappeler indépendamment de tout affect, de toute émotion, sans aucun moi ni surmoi. 9 fois 8 ? La réponse est immédiate, mécanique, purement informative. La façon dont tous ces éléments de connaissance, sur lesquels notre raison s’appuie, sont emmagasinés dans notre mémoire à long terme constitue l’une des grandes énigmes scientifiques que ce siècle aura à résoudre. À partir de quelques hypothèses fortement réductionnistes, néanmoins biologiquement plausibles, un début de réponse peut être trouvé en faisant appel aux développements les plus récents de la théorie de l’information et du codage redondant distribué. C’est ce que cette conférence se propose de démontrer, en combinant différents concepts issus de la neuroanatomie, du codage réparti et de la théorie des graphes.

Vidéo : http://savoirsenmultimedia.ens.fr/expose.php?id=1187

Mardi 26 mars 2013 à 11h15. Antoine Joux (PRISM)

Logarithmes discrets dans les corps finis. Application en caractéristique "moyenne".

Attention Ce séminaire aura lieu à l' INRIA, 23 avenue d'Italie - Salle Orange- 5ème étage

Résumé: Cet exposé commencera par une introduction aux algorithmes génériques de calcul de logarithmes discrets. Ensuite, nous nous intéresserons aux algorithmes de calcul d'index dans le cas le plus simple: celui de la petite ou moyenne caractéristique. Après une présentation des algorithmes précédemment connus, nous montrerons comment une transformation simple de ces algorithmes permet un amélioration importante de la complexité asymptotique et conduit à de nouveaux records de calcul de logarithmes discrets.

Vidéo : http://savoirsenmultimedia.ens.fr/expose.php?id=1134

Mardi 4 décembre 2012 à 11h15. Gérard Berry (Collège de France)

Composer le temps

Le séminaire sera précédé d'un café à 11 heures. Salle W, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé: En informatique classique, le temps est souvent vu à travers le seul prisme du temps de calcul, et rarement vu comme un objet dont la programmation doit parler directement. Or, l’expression directe du temps est fondamentale pour de nombreuses applications informatiques : la conduite de systèmes physiques en temps réel, le traitement du signal, l’orchestration d’applications Web, ou encore la composition musicale pour les générateurs de sons et instruments électroniques. Ceci vaut plus généralement pour le traitement d’événements répétitifs, assimilables à des temps asynchrones au temps physique. Nous analyserons les questions posées par la représentation du temps et des événements répétitifs en informatique, la façon d’en parler dans les langages de programmation ou les logiques de raisonnement, le type d’applications concernée, et la relation avec les activités de modélisation et de simulation de systèmes.

Vidéo : http://savoirsenmultimedia.ens.fr/expose.php?id=968

Mardi 13 novembre 2012 à 11h15. Laurent Massoulié (Microsoft Research-INRIA)

The Price of Privacy in Untrusted Recommendation

Le séminaire sera précédé d'un café à 11 heures. Salle Dussane, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé: Online privacy concerns prompt the following question: can a recommendation engine be accurate if end-users do not entrust it with their private data? To provide an answer, we study the problem of learning user ratings for items under so-called local differential privacy, a formal notion of data privacy. We obtain lower bounds on learning complexity based on mutual information. These results highlight the role played by the amount of ratings performed by each user. In the information-rich regime (where each user rates at least a constant fraction of items), a spectral clustering approach is shown to achieve optimal sample complexity, as it matches our information-theoretic lower bounds. In contrast, the information-scarce regime (where each user only rates a vanishing fraction of the total item set) is found to require a different approach. We thus propose the so-called "MaxSense" algorithm, which achieves optimal sample complexity in the information-scarce regime. This is based on joint work with Nidhi Hegde (Technicolor) and Siddhartha Banerjee (UT Austin).

Séminaire exceptionnel: Mercredi 17 octobre 2012 à 14h. Adi Shamir (Weizmann)

Improved Algorithms for Composite Search Problems

Amphi Evariste Galois - NIR

Mardi 16 octobre 2012 à 11h15. Alexandre d'Aspremont (École Polytechnique)

Approximation Bounds for Sparse Principal Component Analysis

Le séminaire sera précédé d'un café à 11 heures. Salle Dussane, École normale supérieure, 45 rue d'Ulm, Paris 5ème.

Résumé: We produce approximation bounds on a semidefinite programming relaxation for sparse principal component analysis. These bounds control approximation ratios for tractable statistics in hypothesis testing problems where data points are sampled from Gaussian models with a single sparse leading component.

This is joint work with Francis Bach (INRIA - ENS) and Laurent El Ghaoui (UC Berkeley).

Enregistrement audio : http://savoirs.ens.fr/expose.php?id=1041

Mardi 2 octobre 2012 à 11h15. Michael I. Jordan (Fondation Sciences Mathematiques de Paris, University of California, Berkeley)

Diviser-pour-Régner and Inférence Statistique pour "Big Data"

Le séminaire sera précédé d'un café à 11 heures. salle W, Toits du DMA, Ecole Normale Supérieure, 45 rue d'Ulm, Paris 5e.

Résumé: Dans cet exposé nous présentons quelques résultats récents dans le domaine d'inférence pour "Big Data". Diviser-pour-régner est un outil essentiel du point de vue computationel pour aborder des problèmes de traitement de données à grande échelle, surtout vu la croissance récente de systèmes distribués, mais ce paradigme présente des difficultés lorsqu'il s'agit d'inférence statistique. Considérons, par exemple, le problème fondamentale d'obtenir des intervalles de confiance pour les estimateurs. Le principe du "bootstrap" suggère d'échantilloner les données à plusieurs reprises pour obtenir des fluctuations et donc des intervalles de confiance, mais ceci est infaisable à grande échelle. Si on fait appel à des sous-échantillons on obtient des fluctuations qui ne sont pas à l'échelle correcte. Nous présentons une approche nouvelle, la "bag of little bootstraps," qui circonvient ce problème et qui peut être appliquée à des données à grande échelle. Nous parlerons aussi du problème de complétion de matrice à grande échelle, où l'approche de diviser-pour-régner est un outil practique mais qui soulève des problèmes théoriques. Le soutient théorique est fournit par des théorèmes de concentration de matrices aléatoires, et à ce propos nous présentons une approche nouvelle à la concentration de matrices aléatoires basée sur la méthode de Stein.

[En collaboration avec Ariel Kleiner, Lester Mackey, Purna Sarkar, Ameet Talwalkar, Richard Chen, Brendan Farrell et Joel Tropp].

Enregistrement audio : http://savoirsenmultimedia.ens.fr/expose.php?id=1056

Exposés passés, 2011-2012

Mercredi 6 juin 2012: Yevgeniy Dodis (New-York University)

Recent Progress in Leakage-Resilient Cryptography

14h-15h, amphi Rataud

Résumé: I will survey selected recent advances in the field of Leakage-Resilient Cryptography. This booming area is concerned with the design of cryptographic primitives resistant to arbitrary side-channel attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is somehow "bounded", so that not the entire secret key is leaked.

I will start by surveying recent results in the so called Bounded Leakage Model, where the overall leakage is bounded by some parameter L, and the goal is to make L large relative to the length of the secret key. Then, I will move to the Bounded Retrieval Model, which ensures that the complexity of the scheme is independent of the leakage bound L (e.g., it does not increase when the leakage parameter L grows). Finally, I briefly mention the more advanced Continuous Leakage-Model, where the secret key is periodically refreshed (public key is fixed!), and the amount of leakage is only bounded in between successive refreshes, but is unbounded overall.

Most of the covered material can be found in the survey available here: http://cs.nyu.edu/~dodis/ps/brm.ps

Video : http://savoirsenmultimedia.ens.fr/expose.php?id=918

Mardi 13 mars 2012: Jeff Erickson (University of Illinois at Urbana-Champaign and IST Austria)

Computational Topology of Cuts and Flows

14h-15h, salle W (45 rue d'Ulm, escalier B, 4ème étage)

Résumé: The maximum flow and minimum cut problems have been targets of intense algorithmic research for more than half a century. Although flows and cuts in planar graphs has been studied from the very beginning, relatively little is known about flows and cuts in even slightly more general classes of graphs. I will describe the first algorithms to compute maximum flows and minimum cuts in surface-embedded graphs in near-linear time. Except for the special case of planar graphs, the only previous time bounds for either problem follow from algorithms for general sparse graphs. The key insight in our algorithms is to view flows and cuts through the lens of homology, a standard tool in algebraic topology introduced more than 100 years ago by Henri Poincaré.

This is joint work with Erin Chambers, Kyle Fox, and Amir Nayyeri.

Les transparents de l'exposé et les trois articles de recherche correspondants: Homology flows, cohomology cuts, Minimum cuts and shortest homologous cycles, Minimum cuts and shortest non-separating cycles via homology covers.

Mardi 31 mai 2011: Venkat Anantharam (University of California, Berkeley)

What Risks Lead to Ruin

14h-15h, salle "des conférences" au 46, rue d'Ulm (rdc, à gauche)

Résumé: Insurance transfers losses associated with risks to the insurer for a price, the premium. We adopt the collective risk approach. Namely, we abstract the problem to include just two agents: the insured and the insurer. We are interested in scenarios where the underlying model for the loss distribution is not very well known, and the potential losses can also be quite high. It is then natural to adopt a nonparametric formulation. Considering a natural probabilistic framework for the insurance problem, assuming independent and identically distributed (i.i.d.) losses, we derive a necessary and sufficient condition on nonparametric loss models such that the insurer remains solvent despite the losses taken on. In more detail, we model the loss at each time by a nonnegative integer. An insurer’s scheme is defined by the premium demanded by the insurer from the insured at each time as a function of the loss sequence observed up to that time. The insurer is allowed to wait for some period before beginning to insure the process, but once insurance commences, the insurer is committed to continue insuring the process. All that the insurer knows is that the loss sequence is a realization from some i.i.d. process with marginal law in some set P of probability distributions on the nonnegative integers. The insurer does not know which p 2 P describes the distribution of the loss sequence. The insurer goes bankrupt when the loss incurred exceeds the built up buffer of reserves from premiums charged so far. We show that a finite support nonparametric loss model of this type is insurable iff it contains no “deceptive” distributions. Here the notion of “deceptive” distribution is precisely defined in information-theoretic terms. Note that, even though we assume a finite range for each p 2 P, there is no absolute bound assumed on the possible loss at any time. The necessary background from information theory and risk theory as well as some motivation for the problem formulation will be provided during the talk.

Exposés passés, 2010-2011

Jeudi 17 mars, 2011: Claire Mathieu (Brown University)

How to optimize

14h-15h, amphi Rataud

Résumé: Whether you are picking a route around traffic jams, deciding which of your late tasks are most urgent, planning a cheap but fast trip, dropping bombs on enemy terrain, or deciding how to place passengers' luggage in an airplane, you are optimizing a combinatorial problem. Many of those problems are NP-hard. I will present some ways to solve those hard problems relatively fast, discussing the tradeoff between the time spent and the quality of the resulting solution.

Mardi 8 fevrier 2011: Nigel Smart (CS Dept, University of Bristol, UK).

Attestation: Trying to decipher what it is.

14h-15h, Salle Henri Cartan - Passage Rouge - Niveau -2

Résumé: This talk will summarize some of the ongoing work we have been doing in Bristol in looking at security models for DAA type protocols. The first part of the talk will from a high level view look at what DAA provides and how it differs from standard group signatures. We will look at how the industrial requirements of the TCG standards body conflict with what one would want as a theoretical basis. The second part of the talk will go into more detail of a new security model which tries to address the high level problems raised in the first part.

Mardi 14 decembre 2010: Catuscia Palamidessi (INRIA-Polytechnique).

Quantitative information flow.

14h-15h, Salle W au 4eme étage, escalier B

Résumé: One of the concerns in the use of computer systems is to avoid the leakage of secret information through public outputs. Ideally we would like systems to be completely secure, but in practice this goal is often impossible to achieve. Therefore it is important to have a way to assess the amount of leakage. In this talk, we illustrate the information-theoretic approach to measure the leakage, and various scenario depending on the model of adversary.

Mardi 23 novembre 2010: Marc Pouzet (DI, Ens).

Typage et sémantique des modeleurs de systemes hybrides.

14h-15h, Salle W au 4eme étage, escalier B

Résumé: Les modeleurs de systèmes hybrides tels que Simulink sont très largement utilisés dans le développement de systèmes embarqués. Ceci s'explique, en partie, par la possibilité de programmer dans un langage unique à la fois le contrôleur (discret) et son environnement physique (continu). L'ensemble est ensuite simulé et le code embarqué du contrôleur est produit automatiquement par compilation.

Dans cet exposé, nous montrerons quelques biais dans la sémantique et le typage de modeleurs hybrides existants. Nous considèrerons ensuite un langage synchrone proche de Lustre mais permettant de combiner des équations de suites et des équations différentielles ordinaires (ODE). Le langage est équipé d'un système de type dont le rôle est de séparer statiquement la partie continue (approximée par un solveur numérique) de la partie discrète. Nous proposons de donner une sémantique à l'ensemble et basée sur l'analyse non standard, suivant ainsi une idée de Bliudze et Krob. Celle-ci permet en particulier de clarifier le traitement des enchainements de ``zero-crossing'' dans les modeleurs hybrides.

Ce travail a été réalisé avec Albert Benveniste, Tim Bourke et Benoit Caillaud.

Exposés passés, 2009-2010

Mardi 25 mai 2010: Roberto Di Cosmo (PPS, Paris VII).

Logiciels libres et ingénierie des systèmes complexes.

14h-15h, Salle Henri Cartan - Passage Rouge - Niveau -2

Résumé: L'essor rapide des logiciels libre fait emerger quelques problèmes scientifiques nouveaux, auxquels il faut porter rapidement une reponse en utilisant des résultats de la recherche fondamentale; dans cet exposé on presente quelques résultats dans cette ligne issus des projet Coccinelle et Mancoosi.

Mardi 27 avril 2010 : Igor Shparlinski (Macquarie University, Australie, et ENS, Chaire France Telecom pour la sécurité des réseaux de télécommunications, École Normale Supérieure)

Sum-Product Problem: New Generalisations and Applications

14h-15h30, Salle Henri Cartan - Passage Rouge - Niveau -2

Abstract : We give a brief survey of recent results related to the sum-product problem which dates back to work of Erdos and Szemeredi (1983), where it is shown that for any set A of real numbers, at least one of the sets A+A = {a_1 + a_2 : a_1,a_2 in A} and A A = {a_1 a_2 : a_1,a_2 in A} is large. More recently, Bourgain, Katz and Tao (2006) obtained similar results for sets A in prime finite fields. We outline these and several other recent results in this area and also present a diverse scope of their applications to several other problems. Finally we mention several open problems, some of which are motivated by applications to cryptography.

Mardi 16 mars 2010: Eric Goubault (CEA LIST, MeASI? , Paris).

Un survol sur la topologie algèbrique dirigée: des applications à la théorie de la concurrence.

14h-15h30, salle Celan

Abstract: In the early 90s, quite independently, a number of computer-scientific problems appeared to introduce algebraic topological techniques. These include, truly-concurrent semantics for concurrency, fault-tolerant protocols for distributed systems, rewriting systems theory... Since then, two major phenomena arose: the first one is the apparition of new homotopical/homological theories motivated by applications, in particular "directed topology" in concurrency applications, and the view that topological invariants computations are amenable to "numerical schemes" like approximations (this is now called "applied algebraic topology", and has deep developments in robotics, and in computational geometry). Now, it is reasonable to think that, although most of the development in the field of directed algebraic topology were foundational, and almost purely mathematical during 15 years or so, applications to real-size problems in static analysis of concurrent systems, for instance, are now possible. We will present in this talk some of the major concepts of directed algebraic topology, its historical ramifications (both in applications and theory) and some current applications to state-space reduction in semantics/analysis of concurrent systems.

Mardi 23 février 2010: Vincent Rijmen (KU Leuven, Belgium and Graz Univ. Tech., Austria).

The first 10 years of Advanced Encryption

14h-15h30, salle Henri Cartan

Abstract: About 10 years ago, we designed the block cipher Rijndael in response to NIST's announcement of their initiative to select a new encryption standard (the AES). In 2000, NIST selected Rijndael to become the AES. In this talk, I survey the increasing acceptance and adoption of the AES in various applications. I also talk about situations were it proves difficult to convince people to start using AES. Finally I illustrate the influence of the AES on design philosophies being used to design new cryptographic primitives. This is done by looking at the contenders in NIST's SHA-3 competition, which is in full progress.

Mardi 26 janvier 2010: Jean-Jacques Levy (INRIA, Paris)

Un petit bogue, un grand boum

14h-15h30, salle Cavaillès

En juin 1996, le vol 501 de la fusée Ariane 5 se conclut par une explosion au bout de 39 secondes, due à une erreur dans le logiciel de bord. De novembre 1996 à février 1997, une équipe de l'INRIA a appliqué quelques méthodes élémentaires d'analyse statique au code embarqué, grâce principalement à un analyseur d'alias développé alors depuis plus de 10 ans par Alain Deutsch. Ce travail a eu un grand succès auprès des ingénieurs de l'Aérospatiale (renommée EADS depuis) et a donné plus de confiance dans la validité du code embarqué pour le vol 502 et les vols suivants. Comme indiqué dans Wikipedia, l'intérêt du monde industriel pour des outils d'analyse statique, spécialement pour le développement de logiciels critiques, s'est développé à la suite de l'explosion du vol inaugural de la fusée Ariane 5 à cause d'un Bug informatique, sans doute un des bugs les plus chers de l'histoire. Nous expliquerons les différentes phases de ce travail, déjà vieux de plus de 10 ans.

Mardi 15 décembre 2009: Fredo Durand (CSAIL, MIT)

Fourier to the rescue of Photography and Image Synthesis

14h-15h30 salle Henri Cartan

New analysis of light transport and image formation enables novel imaging strategies that reduce motion blur and depth of field as well as acceleration algorithms for computer graphics.

We analyze phenomena such as light transport in a scene, integration during the shutter interval and defocus blur with the Fourier transform of the domain of light rays and space-time. For imaging applications, this offers both new theoretical insights on upper bounds of achievable sharpness and signal-noise ratio in the presence of motion blur and depth of field as well as new lens and camera designs that, combined with computation, can reduce blur. In image synthesis, similar analysis enables algorithms that use adaptive sampling and novel reconstruction to simulate effects such as motion blur and depth of field with dramatic speedups.

Mardi 24 novembre 2009: Jean-Philippe Vert (École des Mines-Paristech)

Some contributions of machine learning in bioinformatics

14h-15h30, salle Henri Cartan

Many problems in bioinformatics can be formulated as statistical and pattern recognition problems on non-standard objects, such as strings, graphs or high-dimensional vectors with particular structure. They have triggered many original developments in machine learning recently, in particular in the way data are represented and prior knowledge is introduced in the algorithm. In this talk I will present some of these developments through several examples in genomic data analysis and virtual screening.

Mardi 20 octobre 2009: Cristian S. Calude (University of Auckland, New Zealand)

Algorithmic Randomness: A Primer

14h-15h30, Salle des Actes

Measuring and calibrating incompressibility is used to define algorithmically random objects, finite (e.g. bit strings) or infinite (e.g. reals). The talk presents theoretical and experimental recent results that shed new lights on Monte Carlo simulations, mathematical provability and quantum randomness.

Mardi 22 septembre 2009: Adi Shamir (Weizmann Institute)

How Cryptosystems Are Really Broken

14h-15h30, Amphi Rataud

Most of the cryptosystems we currently use are highly secure, and cannot be broken by mathematical cryptanalysis. However, over the last ten years researchers have developed many types of physical attacks on their implementation which can easily bypass their mathematical security. In this talk I will survey some of these techniques, and show how difficult it is to build a truly secure communication system.
Webmaster: webdi[@]di[.]ens[.]fr.