Institut de Recherche en Informatique Fondamentale

IRIF Université Paris 7 CNRS 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.


Prochains séminaires


Mardi 26 septembre 2017 · 11h00 · Salle 1007

Algorithmes et complexité · Vianney Perchet (CMLA, Ens Paris-Saclay) · Online Search Problems

In traditional “search problems”, an agent aims at exploring a graph in order to find a hidden object as fast as possible. We consider here the Bayesian repeated scenario with several iid instance of the same basic search problem. The objective is, within a given amount of time, to find as many objects as possible with the possibility to leave an instance for the next one at any moment.

We also consider the non-bayesian case with a variant of regret minimization. We provide and analyze several algorithms with fast rates of convergence and/or guaranteed efficiency.


Mardi 26 septembre 2017 · 14h00 · Salle 1007

Algorithmique distribuée et graphes · Jara Uitto (ETH Zurich) · Tight Lower Bounds for the Cops and Robbers Game

For the game of cops and robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time and that there exist graphs in which this capture time is tight. When k ≥ 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O( n^(k+1) ), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. We answer the question of Bonato and Nowakowski on the negative, proving that the O(n^(k+1) ) bound is asymptotically tight for any constant k ≥ 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.

Mercredi 27 septembre 2017 · 11h00 · Salle 3052

Séminaire des doctorants · Tba · Séance stagiaires / nouveaux doctorants


Jeudi 28 septembre 2017 · 11h45 · Salle 1007

Combinatoire énumérative et analytique · Eric Fusy (LIX) · Intervalles de Tamari et cartes planaires

La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années. Nous présenterons ici un survol des liens bijectifs avec des familles de cartes planaires, en particulier avec les triangulations (pour les intervalles classiques) et avec les cartes biparties (pour les intervalles dits “nouveaux”), en mettant l'accent sur des symétries de distribution de paramètres que ces bijections révèlent (la partie sur les intervalles nouveaux est basée sur des discussions récentes avec Frédéric Chapoton).