Institut de Recherche en Informatique Fondamentale


IRIF

L'IRIF est une unité mixe de recherche (UMR 8243) du CNRS et de l'Université Paris-Diderot, issue de la fusion des deux UMR LIAFA et PPS au 1er janvier 2016. Ses objectifs scientifiques se déclinent selon trois grandes thématiques au cœur de l'informatique : les fondements mathématiques de l’informatique ; les modèles de calcul et de preuves ; la modélisation, les algorithmes et la conception de systèmes. Voir plus ici.



Prochains séminaires


Mercredi 28 septembre 2016 · 11h00 · Salle 1007

Combinatoire énumérative et analytique · Guillaume Chapuy (IRIF) · Graphes aléatoires dans les classes ajoutables et la conjecture deMcDiarmid-Steger-Welsh.

Soit G_n un graphe aléatoire uniforme à n sommets, choisi dans votre classe de graphes favorite (graphes planaires, graphes sans triangles,graphes 7-coloriables, etc…). Quelle est la probabilité que G_n soit connexe? Sans hypothèse sur la classe on ne peut, bien sûr, rien dire sur cette question. Mais si la classe de graphe est *ajoutable*, àsavoir stable par l'ajout d'arêtes entre composantes connexes, McDiarmid-Steger-Welsh (2005) ont conjecturé que P(G_n connexe) est au moins exp(-1/2)=0.60… asymptotiquement. Cette borne est optimale (car elle est atteinte pour la classe des forêts) et aussi assez étonnante (car de nombreuses classes sont ajoutables, y compris des classes très bizarres sur lesquelles on penserait ne rien pouvoir dire). Je parleraide notre démonstration de cette conjecture. Je commencerai par expliquer la très jolie et simple technique dedouble-comptage due à McSW et qui permet de démontrer la borne exp(-1). Puis j'essaierai de donner les idées principales de notre technique nouvelle, le «double-comptage local». Cette technique débouche sur un problème d'optimisation non convexe dont les fonctionnelles sont par miracle des séries génératrices d'arbres enracinés pondérés par des fonctionnelles supermultiplicatives. L'adaptation d'outils de combinatoire classique (le théorème de disymétrie!) permet de résoudre le problème. Travail commun avec Guillem Perarnau (Birmingham)

Vendredi 30 septembre 2016 · 14h30 · TBA

Automates · Équipe automate · Journée de rentrée

Sylvain Lombardy (LaBRI)– Démonstration du logiciel Vaucuson-R

Lundi 03 octobre 2016 · 11h00 · Salle 1007

Vérification · Giovanni Bernardi (IRIF) · Robustness against Consistency Models with Atomic Visibility

To achieve scalability, modern Internet services often rely on distributed databases with consistency models for transactions weaker than serializability. At present, application programmers often lack techniques to ensure that the weakness of these consistency models does not violate application correctness. In this talk I will present criteria to check whether applications that rely on a database providing only weak consistency are robust, i.e., behave as if they used a database providing serializability, and I will focus on a consistency model called Parallel Snapshot Isolation. The results I will outline handle systematically and uniformly several recently proposed weak consistency models, as well as a mechanism for strengthening consistency in parts of an application.

Mercredi 05 octobre 2016 · 11h00 · Salle 1007

Combinatoire énumérative et analytique · Yann Chiffaudel (LPMA) · Approche macroscopique de la diffusion dans le modèle des miroirs

Dans la littérature mathématique, le mot diffusion fait référence à plusieurs définitions différentes. Je m'intéresse à la diffusion dite “macroscopique” caractérisée par l'existence d'une densité de particules évoluant selon la loi de Fick. Je porterai mon attention sur le modèle des miroirs en dimension 2 et sur sa généralisation en dimension quelconque. Ce modèle de gaz de Lorentz sur réseau permet un énoncé clair et rigoureux de la loi de Fick. Une approche analytique nous a permis de simplifier le problème et de réaliser une étude numérique qui permet de conjecturer la validité de la loi de Fick en dimension 3. Je présenterai l'étude complète de façon très visuelle et abordable.


Événements


Mercredi 7 – Vendredi 9 septembre 2016 · Institut Henri Poincaré (IHP)

Approx-Random 2016


Dimanche 15 - Vendredi 20 Janvier 2017 · Jussieu

POPL 2017



Organismes de tutelle


Université Paris-Diderot – Paris 7

CNRS


UFR de rattachement

Partenaires


Fédération de Recherche en Mathématiques de Paris Centre

Fondation Sciences Mathématiques de Paris

INRIA