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

La personne responsable est Marc Pouzet. Les exposés ont lieu au 45, rue d'Ulm, salle à préciser au cas par cas.

Prochains exposés

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.

---

---

---

Exposés passés

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.

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.

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.