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


Vendredi 22 septembre 2017 · 14h00 · Salle 1007

Catégories supérieures, polygraphes et homotopie · Simon Henry · Les polygraphes non-unitaires et la conjecture de Simpson

Je partirai de deux “théorèmes” faux : Le premier est dû à Kapranov et Voevodsky et dit essentiellement que l'on peut représenter les types d'homotopie par des infini-catégories strictes dont toutes les flèches sont faiblement inversibles. Le deuxième est la preuve par Johnstone et Carboni (et Batanin) que la catégorie des polygraphes est une catégorie de préfaisceaux.

Les deux énoncés sont faux pour des raisons très similaires : à chaque fois l'argument clé est l'argument de Eckmann-Hilton, c'est-à-dire le fait que la composition des endomorphismes de n'importe quelle identité dans une infini-catégorie est strictement commutative. Cette commutativité est incompatible avec les deux affirmations précedentes.

Pour cette raison, il est conjecturé que si l'on travaille dans une situation où il n'y pas d'unité, ou bien où les unités sont faibles ou n'interviennent pas alors ces énoncés deviennent vrais. Dans le premier cas il s'agit de la conjecture de semi-strictification de Simpson qui affirme que les types d'homotopie peuvent être représentés par des infini-catégories strictes “sans identités” qui admettent des identités faibles et des inverses faibles. Dans le deuxième cas il s'agit d'une “conjecture” de Johnstone et Carboni qui dit que la catégorie des polygraphes tels que la source et le but de chaque générateur n'est pas une identité est une catégorie de préfaisceaux.

Dans l'exposé je présenterai une preuve de cette dernière “conjecture” et j'expliquerai en quoi cela pourrait permettre d'arriver à une preuve de la conjecture de Simpson.


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.


Mercredi 27 septembre 2017 · 11h00 · Salle 3052

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