L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris-Diderot, qui héberge deux équipes-projets INRIA.

Les objectifs scientifiques de l'IRIF se situent au cœur de l'informatique, se focalisant sur la conception, l'analyse, la preuve et la vérification d'algorithmes et de programmes, appuyé sur des recherches fondamentales en combinatoire, théorie des graphes, logique, théorie des automates, etc.

L'IRIF regroupe près de 170 personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), et deux sont membres de l'Institut Universitaire de France (IUF).


Maurice Nivat

18.01.2018
IRIF organizes on February the 6th a Scientific Day in memory of Maurice Nivat, professor at Paris Diderot University and a pionneer of theoretical computer science. Please register.

Paris Diderot

09.01.2018
In 2018, two faculty positions are opened at IRIF: one full professor position, and one teaching assistant position.

ITCS

05.01.2018
Lucas Boczkowski and Amos Korman from IRIF, with their co-authors, will present at ITCS 2018 a non-conditional lower bound on information dissemination in stochastic populations. The paper is the first ever to combine an algorithmic lower bound with a biology experiment in collective behavior. https://arxiv.org/pdf/1712.08507

CIFRE

19.12.2017
IRIF and ATOS have started the first Industrial PhD Thesis (CIFRE) on quantum algorithms in France. The PhD candidate Alessandro Luongo is co-advised by Iordanis Kerenidis and Frédéric Magniez.

Amina Doumane

29.11.2017
Amina Doumane was awarded the Gilles Kahn prize for her PhD thesis entitled « On the infinitary proof theory of logics with fixed points » supervised by Alexis Saurin, David Baelde and Pierre-Louis Curien.

Wenjie Fang

29.11.2017
Wenjie Fang was awarded the Honorable Mention of the Gilles Kahn prize for his PhD thesis entitled « Aspects énumératifs et bijectifs des cartes combinatoires : généralisation, unification et application » and supervised by Guillaume Chapuy and Mireille Bousquet-Mélou.

FOCS

15.11.2017
IRIF is happy to host and organize the 59th IEEE Symposium on Foundations of Computer Science (FOCS 2018), at Maison de la Chimie, Paris, October 07-09, 2018.

SODA

06.10.2017
Guillaume Lagarde and Sylvain Perifel have solved a 20-year old conjecture related to Lempel-Ziv. This will be presented at the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

Vérification
lundi 22 janvier 2018, 11h00, Salle 1007
Josef Widder (TU Wien) Synthesis of Distributed Algorithms with Parameterized Thresholds Guards

Fault-tolerant distributed algorithms are notoriously hard to get right. I present an automated method that helps in that process: the designer provides specifications (the problem to be solved) and a sketch of a distributed algorithm that keeps arithmetic details unspecified. Our tool then automatically fills the missing parts. In particular, I will consider threshold-based distributed algorithms, where a process has to wait until the number of messages it receives reaches a certain threshold, in order to perform an action. Such algorithms are typically used for achieving fault tolerance in distributed algorithms for broadcast, atomic commitment, or consensus. Using this method, one can synthesize distributed algorithms that are correct for every number n of processes and every number t of faults, provided some resilience condition holds, e.g., n > 3t. This approach combines recent progress in parameterized model checking of distributed algorithms—which I also address—with counterexample-guided synthesis.

This is joint work with Marijana Lazić, Igor Konnov, and Roderick Bloem.

Algorithmes et complexité
mardi 23 janvier 2018, 10h00, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot
Claire Mathieu - Tim Roughgarden (DI ENS, IRIF - Stanford University) On Game Theory Through the Computational Lens

Seventh lecture from Claire Mathieu at Collège de France on Algorithms (at 10am), followed by a talk from Tim Roughgarden on Game Theory Through the Computational Lens (at 11am).

Additional information: http://www.college-de-france.fr/site/claire-mathieu/course-2018-01-23-10h00.htm

Séminaire des doctorants
mercredi 24 janvier 2018, 11h00, Salle 3052
Alessandro Luongo And Ny Aina Andriambolamalala (Algorithms and complexity team and Combinatorics team) TBA and TBA

TBA and TBA

Combinatoire énumérative et analytique
jeudi 25 janvier 2018, 11h45, Salle 1007
Cécile Mammez (Université du Littoral Côte d'opale) Etude combinatoire des diagrammes de dissection de Dupont

Dans sa thèse de doctorat, Dupont s’intéresse au problème du calcul du coproduit de l’algèbre de Hopf fondamentale dans la catégorie des structure de Hodge-Tate mixte pour la famille des polylogarithmes motiviques de dissection. Pour cela, il introduit une famille d’algèbres de Hopf combinatoires de diagrammes de dissection, dont le produit est donné par l’union disjointe et le coproduit par un procédé d’extraction-contraction à paramètre. Ces outils lui permettent de définir, pour tout entier naturel n, des n-formes méromorphes de C^n et de définir par la suite des intégrales absolument convergentes (périodes).

Pour tout scalaire x, nous notons HD l’algèbre de Hopf graduée connexe des dia- grammes de dissection de paramètre x. Nous nous sommes intéressés au problème de l’étude de sa coliberté. Pour cela nous avons considéré son dual gradué HD*. Il possède une structure pré-Lie. Nous construisons l’unique morphisme pré-Lie entre l’algèbre pré-Lie des arbres enracinés à un générateur et l’algèbre pré-Lie des diagrammes de dissection. Ceci nous permet d’étudier l’algèbre pré-Lie engendrée par le diagramme de dissection de degré 1. Nous obtenons que cette dernière est une sous-algèbre pré-Lie non triviale non libre de l’algèbre pré-Lie des diagrammes de dissection.

Vérification
lundi 29 janvier 2018, 11h00, Salle 1007
Engel Lefaucheaux (ENS Cachan / IRISA Rennes) Probabilistic Disclosure: Maximisation vs. Minimisation

We consider opacity questions where an observation function provides to an external attacker a view of the states along executions and secret executions are those visiting some state from a fixed subset. Disclosure occurs when the observer can deduce from a finite observation that the execution is secret. In a probabilistic and nondeterministic setting, where an internal agent can choose between actions, there are two points of view, depending on the status of this agent: the successive choices can either help the attacker trying to disclose the secret, if the system has been corrupted, or they can prevent disclosure as much as possible if these choices are part of the system design. In the former situation, corresponding to a worst case, the disclosure value is the supremum over the strategies of the probability to disclose the secret (maximisation), whereas in the latter case, the disclosure is the infimum (minimisation). We address quantitative problems (comparing the optimal value with a threshold) and qualitative ones (when the threshold is zero or one) related to both forms of disclosure for a fixed or finite horizon. For all problems, we characterise their decidability status and their complexity. We discover a surprising asymmetry: on the one hand optimal strategies may be chosen among deterministic ones in maximisation problems, while it is not the case for minimisation. On the other hand, for the questions addressed here, more minimisation problems than maximisation ones are decidable.