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).

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.

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

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

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.

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.

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.

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.

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).

Séminaire des doctorants
mercredi 24 janvier 2018, 11h00, Salle 3052
Alessandro Luongo & Ny Aina Andriambolamalala (Algorithms and complexity team & Combinatorics team) Recent updates in quantum machine learning & Election de leader dans un réseau radio simple saut avec detection de collision

*Recent updates in quantum machine learning*

In this talk we are going through some recent algorithms in the field of quantum machine learning. Most of the techniques use tools from quantum algorithmics such as counting, optimizing, estimating distances and singular values which will be introduced here. Using these primitives it's possible to build more complex operations of a matrix algebra. I'll also describe a classical machine learning algoritm in the process of being translated in a fully fledged quantum algorithm. This is the first biologically plausible quantum algorithm with an exponential speedup w.r.t the dimension of the space and the number of datapoints. This quantum algorithm has been simulated and used to classify handwritten digits with high accuracy.

*Election de leader dans un réseau radio simple saut avec detection de collision*

Les résultats de Dan Willard (1986) montrent un algorithme randomizé d'élection de leader en temps moyen $O(\log\log{n})$.

Depuis, la question de savoir s'il existe un algorithme convergeant en temps log-logarithmique mais avec très forte probabilité est ouverte.

Nous répondons affirmativement à cette question. Nous montrons aussi comment utiliser nos résultats pour élaborer des protocoles d'élection dans divers modèles de systèmes distribués.

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.

Preuves, programmes et systèmes
jeudi 25 janvier 2018, 10h30, Salle 3052
Justin Hsu (University College of London) From Couplings to Probabilistic Relational Program Logics

Many program properties are relational, comparing the behavior of a program (or even two different programs) on two different inputs. While researchers have developed various techniques for verifying such properties for standard, deterministic programs, relational properties for probabilistic programs have been more challenging. In this talk, I will survey recent developments targeting a range of probabilistic relational properties, with motivations from privacy, cryptography, machine learning. The key idea is to meld relational program logics with an idea from probability theory, called a probabilistic coupling. The logics allow a highly compositional and surprisingly general style of analysis, supporting clean proofs for a broad array of probabilistic relational properties.

Bio: Justin Hsu is a post-doctoral researcher at the University College of London. He obtained his graduate degree from the University of Pennsylvania. His research interests span formal verification and theoretical computer science, including verification of randomized algorithms, differential privacy, and game theory.

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.

Algorithmes et complexité
mardi 30 janvier 2018, 10h00, Collège de France, Amphithéâtre Maurice Halbwachs - Marcelin Berthelot
Claire Mathieu - Allison Bishop (DI ENS, IRIF - IEX and Columbia University) On Algorithms Operating in Adversarial Conditions

Eighth lecture from Claire Mathieu at Collège de France on Algorithms (at 10am), followed by a talk from Allison Bishop on Algorithms Operating in Adversarial Conditions (at 11am).