The future financial and accounting manager will organise tasks relating to the creation, implementation and monitoring of financial operations for the IRIF, in compliance with the techniques, rules and procedures of the two managing supervisory bodies (CNRS, Université Paris Cité). Come and join us!

irif is recruiting! We have a vacancy for a Financial and Accounting Manager (M/F). Come and join us!We have a vacancy for a Financial and Accounting Management Assistant (M/F).


Delia Kesner, professor at IRIF, won the MSCA Staff Exchange 2023 call for her project “QCOMICAL – Quantum Computing and its Calculi”. The grant fund collaborative projects, promoting personnel mobility among consortium members. “QCOMICAL aims to encourage new developments in the theory of quantum programming languages and foster new interactions between participants to achieve substantial advances beyond the current state of knowledge in quantum computing.”


Paul-André Melliès has been invited as Plenary Speaker at the Logic Colloquium 2024 which will be held 24–28 June at the University of Gothenburg in Sweden. He will speak about his work on higher-order automata and profinite lambda-calculus developed at IRIF in collaboration with Sam van Gool and Vincent Moreau.

Elixir has launched its new version! Giuseppe Castagna (IRIF Senior Researcher) and Guillaume Duboc (IRIF PhD student) developed with José Valim the type-system for this open-source programming language. “This release introduces set-theoretic types into a handful of language constructs.”

The 2024 Alonzo Church Award (EACSL) has been attributed to Thomas Ehrhard (Senior Research Scientist at IRIF - CNRS) and Laurent Regnier. This award is for an outstanding contribution to Logic and Computation. Many congratulations to both of them!

An administrative and financial manager position is available! Do you want to join a friendly team and do you love chocolate? This position is for you!

The 14th Île-de-France Programming Day will take place on Monday, June 10, 2024, at Université Paris Cité, in the Department of Computer Science. This day is an opportunity for a fun and friendly competition between teams of computer science undergraduate students from Université Paris-Saclay, Université Paris Cité, and Sorbonne University. This day is jointly organized by Pierre Letouzey (IRIF), Jean-Baptiste Yunès (UPC), Emmanuel Chailloux (UPMC) and Jean-Christophe Filliâtre (Paris Saclay).

A research engineer position in software development is available. Feel free to share this job offer with those around you!


Ahmed Bouajjani, Professor at IRIF, has been awarded for his contribution to research in the computer science field. He has been nominated in the Scientific Research category for the 6th edition of the “Trophées Marocains du Monde”. Many congratulations!

The rerun of Véronique Cortier Distinguished Talk that was held on February is now available on the IRIF YouTube channel. Her subject was: “Electronic voting: design and formal verification”.


Three scientific outreach projects by IRIF researchers have been selected for the 2024 edition of France-Paris Pint of Science. The idea is to discover a scientific theme or subject in a bar. Our researchers will be talking about data protection, graphs and quantum computing.


IRIF is pleased to announce its second Distinguished Lecture of the year! Our invited speaker is Omer Reingold, professor of computer science at Stanford University and the director of the Simons Collaboration on the Theory of Algorithmic Fairness (Simons Foundation). He will talk about Algorithmic Fairness. Anyone interested is welcome to join us for this talk!


Congratulations to Quentin Aristote, doctoral student, who won the Helena Rasiowa prize for the best student paper at the 32nd EACSL conference: Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids


The Belgian Mathematical Society (BMS) has awarded Mirna Džamonja (CNRS, IRIF, Université de Paris) with the BMS “Godeaux lecture prize”. “The prize is awarded every year, upon proposal from a BMS board member, to a prominent belgian or international mathematician who is invited to give a talk at a conference in Belgium.” Congratulations!


We welcome a new research director at IRIF, Tayssir Touili. Her areas of interest are Malware Detection, Software Verification and Formal Methods. You can meet her in room 4028A.


Marie-Josée Iarifina has joined IRIF to replace Natalia Hacquart as Finance and Accounting Manager. Come and meet her and welcome her to office 4002.


After being increased in September 2023, the budget allocated to the french Higher Education and Research is finally reduced by 904 million euros. The podcast “La Science, CQFD” by France Culture wondered how French research is faring and what direction it is taking. Claire Mathieu, research director at CNRS at IRIF, intervenes.

The 2nd french speaking conference «On éteint, on réfléchit, on discute» organized at Université Paris Cité by François Laroussinie focuses on «Les communs numériques» (“Digital Commons”). Serge Abiteboul and Valerie Peugeot are the invited speakers. It will be held on March 19, 2024, from 4pm to 6pm. This is a free of charge event.

Hugo Herbelin, research director at Inria in IRIF, is organizing the next french speaking Horizon Maths day on the topic: Mathematical Proof and Software Safety. It will take place on Wednesday, March 27, 2024, from 9 a.m. to 6 p.m. at the Henri Poincaré Institute (5 rue Pierre et Marie Curie, Paris 5th), Hermite amphitheater. Free but mandatory registration:

Join IRIF as Financial Management Manager! As part of an administrative team supervised by the Administrative Manager and consisting of 5 staff (including 3 managers under your responsibility), you will organise tasks relating to the preparation, implementation and monitoring of financial operations. Application deadline: Friday 23 February 2024. | Planned start date: 1 March 2024


We are delighted to welcome David Saulpic, Research Fellow at the IRIF. His favourite subject? Algorithms, and more specifically clustering problems. You can meet him in his office 4029A.


What kind of research policy? In an article for the french newspaper l'Humanité, Claire Mathieu explains the importance of research for France and the urgent need to make the field more attractive again, at the risk of driving away young researchers.

How to design algorithms to analyze protocols in electronic voting ? How to define mathematically vote secrecy ? What is at stake ? Read the interview Véronique Cortier granted us before her distinguished talk on 7 February, 2024.

One full professor (professeur des universités) and two associate professor (maître de conference) positions will open at IRIF. Fluency in French is mandatory for these positions. The application deadline is March the 6th 2024 (16h00 - Paris time)


On 23 January, Loïc Peyrot, a doctoral student at the IRIF, was invited to speak on the subject of “Record polymorphism for set-theoretic types” at the IMDEA Software Institute.


Will AIs soon surpass their masters? The beginning of an answer can be found in this article in Le Monde Sciences on the rise of AI in mathematics, in which Vincent Jugé, a lecturer at the Gaspard-Monge Computer Science Laboratory at Gustave Eiffel University and seconded to the IRIF, is quoted.


Congratulations to David Saulpic, who will be joining IRIF on 1 February, winner of the 2023 Gilles Kahn Dissertation Prize! He defended his thesis in 2018, entitled “Approximation Algorithms and Sketches for Clustering”.


Congratulations to Pierre Fraigniaud, who won an Imre Simon Test-of-Time award 2024 for the paper "Collective Tree Exploration" with Leszek Gasieniec, Dariusz R. Kowalski, and Andrzej Pelc. It appeared in the proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004). It will be delivered at the 16th edition of LATIN, in Puerto Varas, Chile, March 18-22, 2024.


Following the adoption of the immigration law by the government, Claire Mathieu resigned from the Presidential Science Council, which was set up on 7 December 2023.

Watch Pierre Letouzey's (researcher at the IRIF) talk, “Hofstadter's G function and beyond! A curious example combining calculations…” as part of the “Proofs and programmes” conference organised at the Institut Henri Poincaré.


Hugo Herbelin (researcher at Inria and the IRIF) talks about “And what if mathematical proofs were nothing other than programmes” as part of the “Proofs and programmes” conference. He himself coordinated the organisation of the conference at the Institut Henri Poincaré.


Frédéric Magniez,CNRS research director at IRIF and former professor at the Collège de France, was the technical president of the « The Blaise Pascal [re]Generative Quantum Challenge » jury. It was organised by Pasqal, in collaboration with Blaise Pascal Advisors, Michelin, GENCI, and Capgemini. In this interview, he explains the objectives of the challenge and the importance of fundamental research in all the solutions found:

On 13 and 14 December 2023, IRIF and IMJ are delighted to host the complexity days 2023. One of the guest speakers will be Sophie Laplante, a university professor at IRIF.

The rerun of the talk of Simon Peyton Jones, first speaker of the 2023-2024 edition of the distinguished talks series is now available on the IRIF Youtube channel.

A series of lectures on cryptocurrencies is being offered by UPCité's Computer Science UFR. On Tuesday 12 December 2023, the subject will be blockchain, to understand how it works and its place in today's economy. Jean Krivine and Rudy Bouguelli will be on hand to talk about the subject. Free admission, amphitheatre 9E at the Halle aux Farines from 4.15pm to 6.15pm!


We are honoured to announce that Claire Mathieu, Director of Research (CNRS) is part of the Presidential Science Council announced on Thursday 7 December 2023. “This group of twelve high-level scientists is to provide advice to the executive to guide its research and innovation policy […]”.


IRIF has the great pleasure to welcome a new researcher (INRIA ISFP): Guillaume Baudart, an expert in on probabilistic and reactive programming languages (language design, semantics, static analysis, compilation, inference).


Sylvain Perifel will defend his habilitation to direct research [HDR] on Monday 4 December 2022 at 2pm in the Pierre-Gilles de Gennes Amphitheatre of the Condorcet building. His subject is L'aléatoire par le prisme des polynômes et de la compression.


IRIF has the great pleasure to welcome a new researcher (INRIA): Gabriel Scherer, an expert in programming languages, with theoretical aspects of type systems, programming language implementation, general programming language concepts, and even some syntactic aspects.

Du mardi 28 novembre au jeudi 30 novembre, nous recevrons à l'IRIF le comité d'évaluation de l'HCERES dans le cadre de l'évaluation de notre laboratoire. Programme


La prochaine édition de Mathématiques en mouvement, conférence proposée par la FSMP, aura pour thème Des preuves et des programmes. Organisée sous la houlette de Hugo Herbelin, elle aura lieu le samedi 2 décembre 2023 de 14h à 18h.

We are very proud to announce that two papers by two IRIF researchers have been selected for the SODA conference! Congratulations to François Sellier and Robin Vacus.

We are very proud to announce that four papers by six IRIF researchers have been selected for the POPL conference! Congratulations to Claudia Faggian and Gabriele Vanoni, Mahsa Shirmohammadi, Giuseppe Castagna, Mickaël Laurent and Gabriel Scherer.


Meet Sarah Winter, our new associate professor at IRIF ! “My goal is to combine traditional synthesis methods with AI methods, to get the best of both worlds.”


We are very proud to announce that five papers by six IRIF researchers have been selected for the CSL conference! Congratulations to Quentin Aristote, Guillaume Geoffroy, Roman Kniazev, Jérémy Ledent, François Laroussinie and Vincent Moreau.

Grâce au travail d'Alexandra Rogova, l'équipe Automates et applications de l'IRIF, en association avec plusieurs équipes externes s'intéressant à la théorie des bases de données (au LIGM, l'ENS, Telecom Paris, etc.), relance le site et la newsletter de « Database Theory in Paris », qui centralise les évènements scientifiques de cette thématique en région parisienne.

Après avoir eux-mêmes suivis la Fresque du Climat, des membres du laboratoire de l'IRIF formeront, en tant que facilitateurs, des élèves de L1 à la Fresque du Numérique vendredi 15 septembre. Cet atelier permet de comprendre en équipe et de manière ludique les enjeux environnementaux du numérique.


Congratulations to Mohammed Foughali, who has published a paper titled “Compositional Verification of Embedded Real-Time Systems”, alongside Pierre-Emmanuel Hladik from Nantes Université/LS2N and Alexander Zuepke from the Technical University of Munich in the Journal of Systems Architecture. You can access the article here:

IRIF is back to school! Today, we are welcoming our 12 new permanent members to our laboratory. As part of this day, they will present their research topics to us.


L'IRIF est très fier d'annoncer que Geoffroy Couteau, chargé de recherche du CNRS, a obtenu un financement pour son projet ERC Starting Grant : “Overcoming Barriers and Efficiency Limitations in Secure Computation”. Pour en savoir plus sur son projet et ses ambitions :


Toutes nos félicitations à Amélie Gheerbrant, maîtresse de Conférences, qui vient d'être nommée Vice-Doyenne (VD) Vies des campus et Vie étudiante au sein de l'Université Paris Cité !

Article Blog Binaire- Contrôle accès Site Porno

Geoffroy Couteau et Pierre-Evariste Dagand ont écrit un texte à quatre mains dans le Blog Binaire du Journal Le Monde. Ils se demandent s'il est possible de contrôler l'accès aux sites pornographiques tout en conservant l'anonymat et les données de l'utilisateur pour protéger les enfants. C'est ici que le “zéro-proof knowledge” rentre en jeux…


Félicitations à Claire Mathieu, nominée au rang de Fellow de l'EATCS ! A cette occasion, l'INSI dresse son portrait et reviens sur sa carrière de chercheuse.

Congratulations to Guillaume Chapuy and Sam Van Gool who have been selected for the ANR respectively for their subjects “Combinatoire des cartes, méandres et multicourbes, et ses interactions” and “Espaces topologiques de types et de termes”.

Les journées annuelles du GT CombAlg auront lieu les lundi 3 et mardi 4 juillet à Paris. Elles seront suivies d'une journée de l'ANR Combiné le mercredi 5 juillet. Lors de cette dernière, vous pourrez y écouter, entre autres, Guillaume Chapuy sur la hauteur des chemins des intervalles de Tamari aléatoires uniformes et Sylvie Corteel sur les sujets Combinatorics of the Delta conjecture at t=-1.


Guillaume Duboc and Giuseppe Castagna have been invited as speakers in the Elixir Podcast. They dive into the prospect of types in the Elixir programming language.


Congratulations to Jean Krivine (IRIF) and Vincent Danos (ENS and CNRS) who have received the Concur Test-of-Time Award (period 2002-2005) for their article “Reversible Communicating Systems”, published at CONCUR 2004. To read their article :

François Métayer

À l’occasion du départ à la retraite de François Métayer, le LHC rendra hommage au spécialiste des polygraphes, de l’homotopie et de la réécriture, animateur d’un groupe de travail mythique sur ces sujets. L’événement aura lieu les 8 et 9 juin 2023 et sera précédé par les journées LHC

The next speaker of the IRIF Graphs seminar is Sebastiano Vigna (Università degli Studi di Milano). The talk will be given in person on Tuesday 9th May at 15h in room 147 Olympe de Gouges on Monotonicity on undirected networks.

Juliette Calvi, la nouvelle assistante de communication de l'IRIF est arrivée depuis la semaine dernière. N'hésitez pas à lui faire part de tous vos besoins en communication ou simplement à aller la rencontrer dans son bureau 4004.

Journées PPS 2023

Le pôle PPS organise ses journées 2023, les 25 et 26 mai prochains, et c'est ouvert à tous.

Claire Mathieu

Claire Mathieu a été citée dans un article du journal “La Croix” : “Intelligence artificielle : “pourquoi sa vision du monde est-elle si biaisée ?


The ANR CoREACT will have its kick-off on Wednesday 19 April. It will be in room 146 and online, open to everyone. Contact Nicolas Behr for the details.

Claire Mathieu

We are proud to announce that Claire Mathieu was named as recipient of an EATCS fellowship for her fundamental contributions to solving theoretical and applied problems in approximation algorithms, online algorithms, and auction theory.

École de Printemps d’Informatique Théorique 2023

The 50th edition of EPIT (École de Printemps d’Informatique Théorique) will have as theme The Kaleidoscope of Complexity Theory and will take place on June 12-16, 2023 at the Vieille Perrotine CAES/CNRS holiday center on the Oléron Island, in France.

Journées Nationales du GDR IM 2023

Les prochaines Journées Nationales du GDR IM (JNIM 2023) auront lieu à l'Université Paris Cité du 4 avril au 7 avril et sont organisées par l'IRIF. Programme et inscription ici.

JACM Articles from 2022

The paper “Decentralized Asynchronous Crash-resilient Runtime Verification” authored by Borzoo Bonakdarpour (MSU), Pierre Fraigniaud (IRIF), Sergio Rajsbaum (UNAM), David Rosenblueth (UNAM), and Corentin Travers (LIS) has been selected in the “sample of [eight] exciting [..] articles on a diverse range of topics that were published in 2022” in the Journal of the ACM (JACM).

Appel à manifestation d'intérêt 2023 - Médiation scientifique

Pour la troisième année consécutive, la Faculté des Sciences d’Université Paris Cité lance un appel à manifestation d’intérêt pour accompagner et soutenir ses membres dans leurs initiatives ayant vocation à rendre accessible un sujet de recherche scientifique à un public non spécialiste. Date limite 20 mars 2023 minuit.

Interview PhD thesis Farzad Jafarrahmani

Farzad Jafarrahmani, former PhD student at IRIF explains his thesis Fixpoints of Types in Linear Logic from a Curry-Howard-Lambek Perspective in this written interview.

Conférence vidéo “Manuel de Cryptanalyse à l’usage de la NSA”

“Manuel de Cryptanalyse à l’usage de la NSA” est une conférence ludique, présentée par Sylvain Perifel – Maître de conférences (Université Paris Cité/IRIF) à l’occasion de l’édition 2022 de la Fête de la Science. Elle retrace et met en pratique les différentes avancées historiques de cette science, du code de César à RSA en passant par les substitutions mono-alphabétiques et par le chiffre de Vigenère.

Shared engineer position in formal methods

Shared engineer position in formal methods, between IRIF, LIPN and LMF. Deadline to apply: 17/03/2023.

Accepted paper STOC 2023

One paper authored by IRIF member will be presented at STOC 2023, June 20-23, 2023 in Orlando, Florida.

International Day of Women and Girls in Science 2023

On February 11, 2023 we celebrated the International Day of Women and Girls in Science. To highlight this special date, 3 interviews from our PhD students: Mouna Safir, Lucie Guillou and Shamisa Nematollahi.

Recrutement Assistant(e) de communication

L’IRIF recherche un(e) assistant(e) de communication pour un contrat CDD de 24 mois. Date limite pour candidater : 28/02/2023. Date prévue d’embauche : 01/03/2023.

ChatGPT on SQOOL TV - Claire Mathieu

Claire Mathieu, CNRS Senior Research Scientist and algorithm specialist, was interviewed on SQOOL TV about ChatGPT. How this AI works, what is at stake and what are its advantages, Claire Mathieu discussed the basics of ChatGPT.

QIP 2023 Best poster award for QuBobs project

Congratulations to Sophie Laplante (IRIF) and the QuBobs project team. Their poster presented at QIP 2023 received the best poster award.

Portrait de thésard - Victor Lanvin

Victor Lanvin, lauréat d’un prix de thèse Génie de la Programmation et du Logiciel 2022 et ancien doctorant à l’IRIF présente sa thèse A Semantic Foundation for Gradual Set-Theoretic Types dans cette interview écrite.

L’Oréal-UNESCO Young Talents award 2023

The deadline to apply to the prestigious L’Oréal-UNESCO Young Talents award 2023 is February 27, 2023.

Postdoc position ANR-VeSyAM

A full-time research associates position is available to work on the ​VeSyAm research project. The position will start in July 2023. Deadline to apply: 12 noon on 15 Feb 2023. Further information in the job description.

Emission Arrêt sur Images

Claire Mathieu, membre de l’IRIF et spécialiste des algorithmes, est intervenue à l’émission Arrêt sur Images autour du ChatGPT. Comment cette IA construit-elle ses textes ? Pourquoi parvient-elle à couvrir à peu près n’importe quel sujet ?

Découpage électoral des circonscriptions législatives en France : Déséquilibres démographiques et contraintes territoriales

Claire Mathieu and 8 other authors co-authored the article "Découpage électoral des circonscriptions législatives en France : Déséquilibres démographiques et contraintes territoriales" about a new perspective for understanding electoral maps, using computational social science to study the criteria which shape how electoral districts are drawn up in France.

Internship proposal at LS2N and IRIF

Internship proposal for Masters student in computer science at LS2N and IRIF in Real-time analysis and verification of ROS2 robotic applications. To apply, please refer to the internship description.

Workshop LAFI'23

LAFI'23, a workshop affiliated to POPL’23 about Languages for Inference, will be held on January 15, 2023, as a bi-located event in Boston and at Université Paris Cité. The Paris antenna will take place in salle Leduc, at the first floor of Saints-Pères building, 45 rue des Saints-Pères, 75006 Paris, from 3pm to 9:30pm Paris time. The The talks of V. Blanchi, G. Caylak, M. Pagani (IRIF), F. Zaiser will happen physically in Paris. Registration is mandatory.

Portrait Marie Albenque

We are very pleased to welcome Marie Albenque, Senior Research Scientist at CNRS. Learn more about her and her work in this written interview.

Ahmed Bouajjani Honorary Doctor

Ahmed Bouajjani (IRIF) figures among the nine new honorary doctors appointed at Faculty of Science and Technology of Uppsala University. His research focuses on verification, specification and semantics for parallel and distributed programs and computer systems.

Prix de thèse de la chancellerie des Universités de Paris

Jonas Landman, former PhD student at IRIF, is the 2022 winner of a thesis Prize from Chancellerie des Universités de Paris. His thesis “Quantum Algorithms for Unsupervised Machine Learning and Neural Networks” was awarded in the All Specialties Science Prize Category.

One-year visitor - Lauren K. Williams

We are happy to host Lauren K. Williams for a one-year visit at IRIF. To know more about her and her research, read her interview.

Accepted paper ITCS 2023 - Sophie Laplante

Sophie Laplante (IRIF) and Anupa Sunny (IRIF) will present at ITCS 2023 their paper Certificate Games in which players are given inputs x, y such that f(x)\≠f(y). Their goal is to find a position where the bits of their inputs differ. This simple new game can be used to give bounds on query complexity, block sensitivity and several other complexity measures.

Prix informatique Lovelace-Babbage 2023

Le prix informatique Lovelace-Babbage de l’Académie des Sciences 2023 récompense des scientifiques dont les travaux, des plus théoriques aux plus appliqués, contribuent à la création des nouvelles technologies. Date limite pour constituer son dossier de candidature : 10 décembre 2022.

Conference CAP 2022

Nicolas Behr (IRIF) and Paul-André Melliès (IRIF) will speak at the CAP 22 conference which will take place at IHES on Monday 28 and Tuesday 29 November. The registration to the conference is free but mandatory.

Accepted papers ITCS 2023

3 papers coauthored by IRIF members will be presented at ITCS - Innovations in Theoretical Computer Science 2023.

The EQSI is launched

On November 8th, Iordanis Kerenidis (IRIF) and 5 other founding members officially launched the EQSI-European Quantum Software Institute with a stakeholder event in Paris. This initiative aims to further align development processes and jointly achieve responsible innovation in Europe for Quantum Software and Quantum Algorithms, through co-creation with industry and Quantum Hardware partners.

Synthèse nationale des Mathématiques

Le Hcéres a publié la synthèse nationale et de prospective sur les mathématiques. Cette synthèse est constituée de trois volumes fruit d’un travail inédit mené pendant 2 ans par le comité d’experts dont fait partie Valérie Berthé (IRIF). Volume 1 : Rapport principal. Volume 2 : Analyse disciplinaire et des interactions scientifiques. Volume 3 : Caractérisation des publications dans le monde et en France.

Assises des Mathématiques

Les Assises des Mathématiques se déroulent à la Maison de l’Unesco du 14 au 16 novembre 2022. Valérie Berthé et Claire Mathieu, deux membres de l’IRIF, sont intervenues respectivement à la Table ronde sur la Synthèse nationale des Mathématiques et à la Table ronde sur les interactions entre les Mathématiques et les autres sciences.

Accepted papers SODA 2023 - Guillaume Chapuy

Guillaume Chapuy (IRIF) and Guillem Perarnau (Universitat Politècnica de Catalunya) will present, at SODA 2023, their paper proving that almost all automata with n states have a reset word not much longer than √n. This is based on a structure result saying that almost all automata are w-trees (i.e., the w-transitions induce a tree), for some very short word w — whose length is only logarithmic.

Accepted papers SODA 2023 - Adrian Vladu

Lucas Pesenti and Adrian Vladu (IRIF) will present, at SODA 2023, their paper Discrepancy Minimization via Regularization. They make progress towards conjectures in discrepancy theory by showing that Newton's method can produce low discrepancy colorings.

Nomination IUF - Olivier Carton

Congratulations to Olivier Carton (IRIF), head of the pole Automata, structures and verification at IRIF and recently appointed senior member of Institut universitaire de France (IUF). He is interested by the links and connexions between normality and automata.


The FRAIGNIAUD workshop (Fundamental Research and Algorithmic Innovations in Graphs, Networks and the Internet, with Applications and Upcoming Directions) will take place in Paris on the 28th and 29th of November, on the occasion of Pierre FRAIGNIAUD’s 60th birthday.

Lauréat Prix de thèse de la Chancellerie des Université de Paris

Jonas Landman, former PhD student at IRIF is the 2022 winner of the Thesis Prize Chancellerie des Universités de Paris. His thesis entitled Quantum Algorithms for Unsupervised Machine Learning and Neural Networks was awarded in the All Specialties Science Prize Category.

Accepted papers SODA 2023

2 papers coauthored by IRIF members will be presented at SODA 2023, January 22-25. Complete list of accepted papers here.

Gaëtan Douéneau-Tabot lauréat 2022 Best Student Paper Awards

Gaëtan Douéneau-Tabot, doctorant en 3ème année à l’IRIF, est lauréat 2022 de deux Best Student Paper Awards remis par les deux principales conférences organisées par l’EATCS : ICALP et MFCS. En juillet 2022, il a reçu le Best Student Paper Award track B à ICALP et en août 2022, il a reçu un second prix à la conférence MFCS. Il nous explique sa recherche dans cette interview écrite.

National Prize of Computer Science - Mexico

Sergio Rajsbaum, a one-year visitor at IRIF, has received the Computer Science National Prize of Mexico. His research mainly focuses on distributed computing systems: what can be done as a system? What are the limits? Learn more about him and his work in this written interview.

Onglet médiation

L'IRIF inaugure un nouvel onglet “Médiation” sur son site web. Cet onglet rassemble les activités et projets de médiation scientifique organisés par le laboratoire. Vous y trouverez les informations autour de la Fête de la Science, les stages scolaires d'observation, l'exposition sur les 50 ans d'informatique théorique et le projet QuBOBS de Sophie Laplante.

IRIF Hal Collection

IRIF now has a HAL webpage, an open archive where authors can deposit scholar documents from all academic fields.

Postdocs positions at IRIF

Various postdoc positions available at IRIF : several openings in the Algorithms and Complexity group and a 14-month position available in the Polymorphic records in Elixir project.

QuanTech Seminar Cycle - Fall 2022

A new QuanTech Seminar Cycle will take place on October 14, 21, 28 and December 2nd. The seminars provide an overview of the different approaches to implementing quantum technologies ranging from aspects of physics to computer science, and from academic to industrial research.

Fête de la Science 2022 - Parcours quantique

Les 13 et 14 octobre 2022, l'IRIF et le laboratoire MPQ ont proposé aux classes de lycée un parcours quantique A la Découverte des Technologies Quantiques incluant une conférence sur la cryptographie, un atelier sur le protocole BB84, un atelier sur les ions piégés et un autre sur les photons intriqués.

Fête de la Science 2022 - Initiation à l'informatique

Du 7 au 17 octobre 2022, l’IRIF et l’UFR d’Informatique ont accueilli une dizaine de classes de fin primaire-début collège dans le cadre des activités de la Fête de la Science. Au programme, un baptême de programmation et plusieurs îlots de jeux pour s’initier à l’informatique en s’amusant. Plus d’informations sur notre page dédiée à la Fête de la Science.

Portrait Sylvain Douteau

We are very pleased to welcome Sylvain Douteau, Associate professor at Université Paris Cité. Learn more about his work in this written interview.

Interviews FSMP à ICALP 2022

The FSMP was present at ICALP 2022 this summer and took the opportunity to meet the computer scientists Patrick Cousot (New York University), winner of the EATCS prize, Leslie Ann Goldberg (Oxford University), plenary speaker, Craig Gentry (IBM Research), Zvika Brakerski (Weizmann Institute of Science) and Vinod Vaikuntanathany (University of Toronto), winners of the Gödel prize, Gaëtan Douéneau (PhD student at IRIF), best student paper award, and Geoffroy Couteau(IRIF), member of the organization of this edition. All the videos interviews here.

Thomas Ehrhard

Thomas Ehrhard, CNRS senior researcher at IRIF, turned 60 in 2021. A meeting will take place in Paris, at the CNAM, on 29-30 September 2022 to celebrate Ehrhard’s contributions to logic and the semantics of programming languages. For more information, follow the arrow:

Test of Time Award - LICS'22

Philippe Schnoebelen (LMF), François Laroussinie (IRIF) and Nicolas Markey (IRISA), received the Test-of-Time award at the conference LICS 2022 for their research on temporal logic.

ICTP-EAUMP School on Mathematical Programming and Algorithms

IRIF is a co-sponsor of the ICTP-EAUMP School on Mathematical Programming and Algorithms - an African Mathematical School. The 2022 summer school organized by the University of Nairobi took place at Kenya School of Government, Nairobi, Kenya 11-29 July, 2022. Three IRIF members took part of this project: Jean-Baptiste Yunès, Roberto Mantaci and Anna Vanden Wyngaerd.

Prix Irène Joliot-Curie 2022

Plus que quelques jours pour déposer votre candidature au Prix Irène Joliot-Curie, ce prix qui vise à promouvoir la place des femmes dans la recherche et la technologie en France. Clôture des candidatures le 8/09/2022.

Podcast DECODE quantum

Pour son 48ème épisode, le podcast DECODE Quantum a reçu le directeur de l'IRIF Frédéric Magniez dans un entretien approfondi sur le quantique. Il est question, entre autres, d'algorithmes quantiques, de leur intérêt et de leur construction. Par ici pour écouter l'émission.

Workshop CoA 2022

The 2nd Workshop Complexity and Algorithms (CoA 2022) will take place in September 26-28 2022 at Institut Henri Poincaré (IHP), Paris. Scientific program includes talks from invited speakers Marthe Bonamy (LaBRI), Carola Doerr (LIP6), Sébastien Tavenas (LAMA) and Adrian Vladu (IRIF).

ETAPS 2023

The next ETAPS conference, a forum of top-conferences in computer science, will happen in Paris, April 22-27 2023. Paper submission is opened until October 13, 2022, 23:59 AoE.

Création du prix Lovelace-Babbage

L’Académie des sciences et la Société informatique de France annoncent la création d’un nouveau prix en informatique : le prix Lovelace-Babbage.

Baptiste Louf Prix de Thèse

Baptiste Louf, a former IRIF PhD. student is the 2021 winner of the Chancellerie des Universités de Paris thesis award in the “all specialties” science category. Learn more about his work in this written interview.

Accepted paper PODC 2022 R. Vacus & A. Korman

Amos Korman (IRIF) and Robin Vacus (IRIF) presented at PODC'22 their paper studying agreement processes in stochastic environments using minimal communication, inspired by biological scenarios.

Interview ICALP Leslie Ann Goldberg

Leslie Ann Goldberg, invited speaker at ICALP 2022 was interviewed by La Recherche about some of the key issues she is interested in.

Prix de Thèse Gilles Kahn 2022

Le prix de thèse Gilles Kahn récompense chaque année une excellente thèse en informatique. Sont éligibles toutes les thèses soutenues au sein d’établissements français entre le 1er Septembre 2021 et le 31 Août 2022. Date limite de dépôt des candidatures : 16 septembre 2022.

The EAPLS Best Paper Award 2022

The European Association for Programming Languages and Systems (EAPLS) has established a Best PhD Dissertation Award in the research area of programming languages and systems. Candidates for the award must be nominated by their supervisor. Deadline for nominations : 30 August 2022.

Horizon Europe for Beginners

Pierre Fraigniaud, Senior Research Scientist at IRIF/CNRS, Maximilien Lesellier, Head of Administration at IRIF, and Afonso Ferreira, Europe scientific advisor for INS2I at CNRS have written a short document aiming at helping researchers to navigate in the Horizon Europe programme from a researcher perspective.

Accepted paper FLOC 2022

A paper authored by Ahmed Bouajjani (IRIF), Wael-Amine Boutglay (IRIF and UM6P-CS), and Peter Habermehl (IRIF), will be presented on August 7 at the 34th Intern. Conf. on Computer Aided Verification (CAV) – August 7-11: Data-driven Numerical Invariant Synthesis with Automatic Generation of Attributes.

CSGT 2022

Zhouningxin Wang (IRIF) will present “Circular Flows in Mono-directed Eulerian Signed Graphs” at the 8th Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications. The talk is based on a joint work with J. Li (China), R. Naserasr (IRIF), and X. Zhu (China).

Accepted paper P. Fraigniaud PODC 2022

P. Fraigniaud (IRIF) and A. Paz, S. Rajsbaum will present at PODC'22 their paper A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement.

2022 Knuth Prize Award

The 2022 Donald E. Knuth Prize is awarded to Noga Alon, Professor of Mathematics at Princeton University and Emeritus Professor of Mathematics and Computer Science at Tel Aviv University, for foundational contributions in combinatorics and graph theory and applications to fundamental topics in computer science.

PhD in cyber-physical systems, verification, learning

A fully funded PhD position in Computer Science with the subject “Cyber-physical systems with AI components: modeling, learning and verification” opens in IRIF, Paris, within the Modeling and verification team, in the framework of the Franco-Japanese research project CyPhAI.

ETAPS 2023 1st joint call for papers

ETAPS 2023: 1st joint call for papers of the 26th European Joint Conferences on Theory and Practice of Sofware. Paper submission is opened until October 13, 2022, 23:59 AoE.

Accepted paper FPSAC 2022

One paper coauthored by Enrica Duchi (IRIF) and Corentin Henriet (IRIF) will be presented at FPSAC 2022, the 34th International Conference on Formal Power Series & Algebraic Combinatorics, 18-22 July: Combinatorics of fighting fish, planar maps and Tamari intervals.

Accepted paper FOCS'22

One paper coauthored by Simon Apers (CNRS, IRIF) will be presented at FOCS 2022, the 63rd IEEE Symposium on Foundations of Computer Science, October 31 - November 3 in Denver, USA.


MFPS 38 will be held on July 11–13, 2022, with a co-located event in Ithaca, NY, USA, and at IRIF in Paris, France. The talks of A. Goy, W. Heitjtjes, B. König, N. Munnich, D. Petrisan, F. Pfenning, A. Tosun, and N. Wu will take place in room 3052 at IRIF. The talks from speakers in Ithaca and online will be broadcast from 14:30 to 21:30. Registration is mandatory.

ICALP 2022

ICALP 2022 is organised by IRIF and is taking place on July 4–8 on the Grands Moulins campus of Université Paris Cité. This edition marks the 50th anniversary of the conference and of the EATCS.

Conference Highlights 2022

The 2022 edition of Highlights will happen from June 28th to July 1st, 2022, in Paris, France. The conference will be hosted by Université Paris Cité, and happen on the site of Grands Moulins. To register, please fill in the registration form. If you wish to watch Highlights remotely, please fill in the online registration form. Online attendance is free.

Four papers coauthored by IRIF members will be presented at the conference TYPES'22, the main conference on type theory, this summer.

IRIF is co-organizing a Workshop Labyrinth of Combinatorics in memory of Pierre Rosenstiehl, June 15-17, Université Paris Cité

IRIF is co-organizing a Workshop on Differentiable Programming, June 29-30, Université Paris Cité.

Two papers coauthored by IRIF members will be presented at the conference ISSAC'22, the main conference on symbolic and algebraic computation , this summer.

Institut Universitaire de France

IRIF is proud to announce that Olivier Carton, professor of Université Paris Cité and researcher at IRIF, was appointed senior member of IUF.

Four papers coauthored by IRIF members will be presented at the conference PODC'22, the main conference on distributed computing, this summer.

Program of the evening 75 years

On May 9th at 6pm will be held the festive evening of 75 years of computer science, from its foundations to its impact on society. This event is organized by LIP6 with the help from IRIF. Program and details of the evening here.

Accepted paper ICALP 2022

Antonio Casares (IRIF), Thomas Colcombet (IRIF) and Karoliina Lehtinen (Aix-Marseille University) will present at ICALP 2022 their paper studying the link between good-for-games Rabin automata and memory structures for infinite duration games over graphs. They also establish that these automata can be exponentially more succinct than equivalent deterministic ones.

Accepted paper ICALP 2022

Gaëtan Douéneau-Tabot (IRIF, DGA) will present at ICALP 2022 his paper Hiding pebbles when the output alphabet is unary. Pebble transducers are simple programs which compute functions over finite words. This paper studies subclass membership problems for the functions computed by pebble transducers whose outputs are unary. Its results can be understood as program optimization techniques.

ICALP 2022 Accepted papers

3 papers coauthored by IRIF members will be presented at ICALP 2022, July 4-8 in Paris, campus Grands Moulins of Université Paris Cité. Complete list of accepted papers here.


Call for applications: SMARTS-UP International scholarships for Master’s students managed by Université Paris Cité will grant € 8,000 individual scholarships to allow Graduate Schools to welcome international students in their Masters’s programmes. The Graduate School on Quantum Technologies is taking part in this project. Visit the call for applications webpage for more details. Deadline: April 30th, 2022.

ICALP 2022 Registration

Registration to ICALP 2022 is now open. Early registration is open until May 11th, 2022 and late registration starts from May 12th, 2022. For more details and to register, follow this link: https://icalp2022.dakini-pco.com.

World Quantum Day

Today is World Quantum Day! All over the globe, but especially in Europe, many bright minds are researching groundbreaking quantum technologies. This day aims at promoting the public understanding of Quantum Science and Technology around the World.

Interview ICALP 2022 - FSMP

Thomas Colcombet, Geoffroy Couteau et Sylvain Schmitz members of IRIF and part of ICALP 2022 organizing committee were interviewed by FSMP (Fondation Sciences Mathématiques de Paris), one of the co-organizers of the conference. Learn more about the goals of the conference and what makes it special this year (interview in French only).

Cocktail de célébration des 75 d’informatique en France

On May 9th, 2022, LIP6 and IRIF are organizing a cocktail celebrating the 75th anniversary of computer science in France. A panel of experts will explore the discipline from its foundations to its impacts on society.

Teaching Assistant positions

[Update on the calendar] Four Teaching Assistants positions plus three other potential teaching assistant positions that may become available upon contest within UFR d’Informatique of Université Paris Cité fort he academic year 2022-2023. To learn more and to apply, visit: https://www.irif.fr/postes/ater. Deadline to apply, May 4th 2022 (4:00 pm Paris time).

Portrait Mohammed Foughali

IRIF has the great pleasure to welcome a new Associate Professor: Mohammed Foughali, an expert in formal verification and robotics. Learn more about him and his work here.


IRIF will finance one or two additional Master scholarships in Theoretical Computer Science within the PGSM program of FSMP for female students who have completed a bachelor’s degree or the first year masters in one of the universities of the FSMP network. Apply online by May 12th, 2022.

Jeudis du Campus - Modéliser le plafond de verre dans la recherche

How can we model the glass ceiling in research? Claire Mathieu (IRIF) will give a talk on Thursday, March 24th from 1:15 to 2:00 PM as part of Jeudis du Campus. Follow the event live on the CNRS Ile-de-France Villejuif Youtube channel.

PAUSE Program - Solidarity with Ukraine

Reacting to the current situation and supporting the opening of the PAUSE program – Solidarity with Ukraine, few IRIF members have volunteered to host researchers at risk. Contact us at relocation@listes.irif.fr to discuss options for applying to this initiative.

Table ronde Femmes dans le numérique

Tuesday, March 15 at 6 :30 pm on the campus Pierre et Marie Curie, Isabelle Collet (Université de Genève), Christine Tasson (LIP6), Anne Siegel (IRISA)and Alexis Kauffmann (Direction du numérique pour l’éducation) will exchange on a roundtable discussion about inequalities regarding the presence of women in the digital sector.

Table ronde Naissance de l'Intelligence Artificielle

Thursday, March 10 at 6 :30 pm on the campus Pierre et Marie Curie, Jean-Gabriel Ganascia, Jean-François Perrot, and Gérard Sabah will meet to discuss artificial intelligence. Where, when and how did this notion start? All details here.

Accepted paper STACS 2022 | Sander Gribling

Sander Gribling (IRIF) and Harold Nieuwboer (University of Amsterdam) will present at STACS 2022 their paper Improved quantum lower and upper bounds for matrix scaling in which they show classical second-order methods together with quantum spectral sparsifiers lead to faster quantum algorithms for the matrix scaling problem, in the poly(1/eps)-regime.

Accepted paper STACS 2022 | Michel Habib

Pierre Bergé, Guillaume Ducoffe and Michel Habib (IRIF) will present their paper Subquadratic-time algorithm for the diameter and all eccentricities on median graphs at the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) held in Marseille, March 15-18 2022.

Journée internationale des femmes et des filles de science 2022

Aujourd’hui, nous soulignons la Journée internationale des femmes et des filles de science avec 3 interviews de nos doctorantes et post-doctorantes : Ada Vienot, Klara Nosan et Anna Vanden-Wyngaerd.

Nouveau poste maître·sse de conférences

Un poste de Maître·sse de Conférences (références Galaxie no 204) en Mathématiques et informatique fondamentale est à pourvoir à l’UFR de Mathématiques de l’Université de Paris en vue d’une intégration à l’IRIF. Postuler sur Galaxie au plus tard le 28 février 2022 16h (heure de Paris). Prise de fonction le 1er novembre 2022 (si besoin, le laboratoire pourra fournir un CDD du 01/09/2022 au 31/10/2022). Plus de détails sur https://www.irif.fr/postes/universite.

Prix de thèse de la chancellerie des Universités de Paris

Baptiste Louf (currently doing his postdoc in Sweden), received the Thesis Prize The Chancellerie des Universités de Paris category science “all specialties” for his thesis prepared at IRIF under the supervision of Guillaume Chapuy and entitled Cartes de grand genre : de la hiérarchie KP aux limites probabilistes.

Coq Prix Logiciel Libre de la Recherche

The software Coq, a formal proof management system developed by teams at Inria and IRIF was rewarded by the Open Science Awards for Open Source Research Software category Scientific and Technical quality. Learn more about this software: https://coq.inria.fr.

Deadline CFP ICALP 2022

The deadline to submit your paper at ICALP 2022 is February 10, 2022 AoE. Link to submission (track A and B) here. More info on the submission guidelines here.

ICALP 2022

IRIF is excited to organize the next ICALP conference. The 2022 edition will take place in Paris 4-8 July. Visit the website for more info : https://icalp2022.irif.fr. It will be the occasion to celebrate the 50th anniversary of both EATCS and the first ICALP which was held in Rocquencourt in 1972.

Portrait Simon Apers

IRIF has the great pleasure to welcome a new CNRS Research Scientist: Simon Apers, an expert in quantum computing. Learn more about him and his work here

Accepted papers STACS 2022

Two papers coauthored by IRIF members will be presented at the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) held in Marseille, March 15-18 2022.

Accepted paper POPL 2022

Paul-André Melliès (IRIF), Arthur Vale, Zhong Shao, Jérémie Koenig (Yale) and Léo Stefanesco (MPI) will present a layered concurrent object-based game semantics for the purpose of compositional software specification and certification at annual Symposium on Principles of Programming Languages, POPL2022 : https://hal.inria.fr/hal-03456034.

IFIP nomination fellow

Jacques Sakarovitch (IRIF) was elected new IFIP Fellow. IFIP Fellow is the most most prestigious IFIP's technical distinction which is conferred by the IFIP General Assembly on a current or past member of an IFIP body in recognition of outstanding contributions in the field of information processing, in the role of a Technical Leader, Scientist, Engineer, or Educator.

Accepted paper POPL 2022

Delia Kesner (IRIF) will present her paper A Fine-Grained Computational Interpretation of Girard’s Intuitionistic Proof-Nets at annual Symposium on Principles of Programming Languages, POPL2022. The paper introduces a functional term calculus that captures the essence of the operational semantics of Intuitionistic Linear Logic Proof-Nets with a faithful degree of granularity, both statically and dynamically.


IRIF is very pleased to host for two months Serge Massar, Professor at the Université libre de Bruxelles (ULB) as part of the FSMP Distinguished Professor Fellowship. Serge Massar is the director of the Laboratoire d'Information Quantique (LIQ), of the Physics Department, Science Faculty, ULB. His research interests are quantum information theory, experimental quantum and non linear optics, machine learning.

hpcqs project

We are excited to be part of the “High-Performance Computer and Quantum Simulator hybrid” (HPCQS) aiming at creating a world-class supercomputing ecosystem. Learn more about the project here.


Prochaine conférence dans le cadre des 75 ans d’informatique : L’informatique dans le 7ème art : fiction ou réalité ? Rendez-vous avec Fabrice Kordon le jeudi 9 décembre-18h00 sur le campus Pierre et Marie Curie de Sorbonne Université (tour 25.26, 1er étage – salle 105).

Portrait Matej Stehlik

IRIF has the great pleasure to welcome a new professor in computer science at Université de Paris: Matěj Stehlík, an expert in graph theory. Learn more about him and his work here.

Accepted paper FOCS 2021

Adrian Vladu's paper Faster Sparse Minimum Cost Flow by Electrical Flow Localization, jointly written with Kyriakos Axiotis and Aleksander Madry, will be presented at FOCS 2021.

Giuseppe Castagna (IRIF), Mickaël Laurent (Université de Paris), Kim Nguyen (Université Paris Saclay) and Matthew Lutze (Université de Paris) will present their paper that shows a nifty way to use classic deduction rules to define a formal framework in which dynamic languages such as JavaScript can statically and precisely typed. Check the proof-of-concept implementation available at

Accepted papers POPL 2022

Three accepted papers coauthored by IRIF members will be presented at POPL 2022, the main conference on programming languages and programming systems, January 16-22.

Journée du pôle ASD 2021

On November 16th, afternoon, the pole ASD organizes an event. Short introduction talks by the four new ASD permanent members will be presented. There will also be an informal introduction of PhD students and postdocs. Schedule and details of the talks here.

Accepted paper NeurIPS 2021

One accepted paper coauthored by Adrian Vladu (IRIF), Alexandra Peste (IST Austria), Eugenia Iofinova (Institute of Science and Technology Austria) and Dan Alistarh (IST Austria & NeuralMagic) will be presented at the 35th Conference on Neural Information Processing Systems (NeurIPS) 6-14 December 2021 : AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks.

Journée pôle ASV 2021

The Automata, Structures, and Verification (ASV) day is scheduled this year on Friday November 19th. This will be the opportunity to meet again and learn about some of the work done in our pole, in particular by the new comers. Schedule and details of the talks here.

PGSM Master 2022

IRIF will finance one or two additional Master scholarships in Foundations of Computer Science within the PGSM program of FSMP for female students who have completed a bachelor’s degree or the first year masters in one of the universities of the FSMP network. Apply online by February 24th, 2022.

Stage d'observation-3eme

Tous les ans, l’IRIF accueille des élèves dans le cadre de leur stage d’observation de 3ème. Les stages proposés constituent une découverte de l’informatique et des métiers académiques correspondants, qu’ils soient au CNRS ou à l’université de Paris. Toutes les informations pour envoyer sa candidature ici.

Test of Time Award – RV’21

Eugene Asarin (IRIF), Alexandre Donzé, Oded Maler, and Dejan Nickovic receive the Test of Time Award at the 21st International Conference on Runtime Verification (RV’21) for their paper Parametric Identification of Temporal Properties. Watch the RV’21 Award Announcement here.

Journée de rentrée PPS 2021

PPS is holding its journée de rentrée on October 13-14, 2021. This year PPS has 13 new members. The aim of this get-together is to know them and their research topic. Schedule and details of the talks here.

Ateliers-FDSL 2021

IRIF researchers are participating to the 30th edition of Fête de la Science. In different schools in Paris, they will be presenting workshops and games related to computer science.

Fête de la Science 2021 - Conference learning about cryptography

From ancient history to quantum, learn about cryptography at Fête de la science in an entertaining talk by Sylvain Perifel (IRIF). Save the date, Monday October 4th, 10am at Amphitheater 1A, Halle aux farines - Campus Grands Moulins.

Oded Maler Best Paper Award

Eugene Asarin (IRIF), Thomas Ferrère, Dejan Ničković and Dogan Ulus receive the Oded Maler best paper award in Timed Systems at the conference Formats’2021 for their paper On the complexity of timed pattern matching.

Sergio Rajsbaum - visitor at IRIF

IRIF is very pleased to host for three months Sergio Rajsbaum, full time Researcher at the Instituto de Matemáticas of the Universidad Nacional Autónoma de México. This collaboration focuses on the use of algebraic topology to study the complexity of distributed algorithms. Algebraic topology tools have been mainly used for shared memory models. The purpose of the visit is to extend this research to distributed memory models. Professor Rajsbaum is partially funded by an invitational program from École Polytechnique. Meet him in office 4028a.

Accepted paper Eurocomb 2021 - Yiting Jiang

Yiting Jiang (IRIF) and Jaroslav Nešetřil will present a result that there are infinitely many minimal asymmetric k-uniform hypergraphs.


Reza Naserasr (IRIF) is an invited speaker at the 29th Workshop on Cycles and Colourings. He will present a joint work with Lan Anh Pham (IRIF), Zhouningxin Wang PhD student (IRIF) and Xuding Zhu (University Jinchua): Density of C –4 -critical signed graphs. There is a classic one-to-one correspondence between (2k+1)-colorability of a graph and mapping of a specific subdivision of it to the (2k+1)-cycle. In this work they present an extension of this to 2k-coloring using homomorphisms of signed graphs.

Accepted paper Scientific Reports

Amos Korman et Robin Vacus (IRIF) publient On the Role of Hypocrisy in Escaping the Tragedy of the Commons dans la revue Scientific Reports. Dans cet article, ils étudient l'émergence de la coopération dans le cadre formel de la théorie des jeux. Ils considèrent 3 comportements stéréotypés : “tricheur”, “hypocrite” et “coopératif”, et un modèle de pression sociale.

Accepted paper Eurocomb 2021 - Naserasr-Wang

Reza Naserasr and Zhouningxin Wang (IRIF) will present the notion of circular coloring of signed graphs, as a common extension of the circular coloring of graphs and the 0-free coloring of signed graphs. In this work, they consider the problem of finding the best upper bound of the circular chromatic number of restricted families of signed graphs. In particular, they show that every signed bipartite planar graph of negative-girth 6 admits a circular 3-coloring.

Accepted paper Eurocomb 2021 - Aubian-Charbit

Guillaume Aubian, Pierre Charbit (IRIF) and Pierre Aboulker study the class of oriented graphs such that the out-neighbourhood of any vertex induces a transitive tournament and prove for it a decomposition theorem. As a consequence, they obtain that oriented graphs in this class have dichromatic number at most $2$ and satisfy Caccetta-Häggkvist conjecture.

EUROCOMB 2021 - Three papers coauthored by IRIF PhD students

Three papers coauthored by IRIF Ph.D students will be presented at the European Conference on Combinatorics, Graph Theory and Applications. Topics include oriented graphs, asymmetric hypergraphs and bipartite planar graphs.

Presentation Category Theory Conference

El Mehdi Cherradi (IRIF) and Paul-André Melliès (IRIF) will present at Category Theory Conference 2021 their work on derivators, a clever tool introduced by Grothendieck to compute homotopy limits and colimits of spaces, exploring the idea that derivators should be understood as generalised categories.

Publication dans PLOS Computational Biology

Claire Mathieu (IRIF) et ses collaborateurs publient les résultats de leur recherche Mitigating COVID-19 outbreaks in workplaces and schools by hybrid telecommuting dans le journal PLOS Computational Biology. Cet article l'impact de deux stratégies, dites de rotation et d’alternance, pour freiner l’épidémie de Covid-19 que ce soit dans une école ou un bureau. Lire l'article complet ici et le communiqué de presse du CNRS ici.

CONCUR Test-of-Time Award

Ahmed Bouajjani (IRIF), Javier Esparza, and Oded Maler have received the Concur Test-of-Time Award (period 1996-1999) for their article Reachability Analysis of Pushdown Automata: Application to Model-checking published at CONCUR 1997. Read the interview.

86th séminaire Lotharingien de Combinatoire

Dans le cadre d’un mini-cours donné au 86ème séminaire Lotharingien de combinatoire, Guillaume Chapuy (IRIF) parlera d'un nouveau point de vue sur la correspondance entre cartes et tableaux de Young, qui joue un rôle fondamental en combinatoire algébrique. Ce nouveau point de vue, développé dans le cadre des polynômes de Jack et des surfaces non-orientables, est issu de ses travaux avec Maciek Dołęga (ancien postdoctorant à l'IRIF/LIAFA).

Talk SIAM 2021

Sander Gribling and Sven Polak (CWI) will present their ongoing work about the mutually unbiased bases problem. “What is the largest number of mutually unbiased bases in dimension d? We make progress on answering this fundamental question in quantum information theory using semidefinite programs and representation theory”.

Réalisation d'une Synthèse Nationale des Mathématiques

Le Hcéres lance la réalisation d’une synthèse disciplinaire nationale consacrée aux mathématiques. Valérie Berthé (IRIF) fait partie du comité des 16 personnalités chargées de rédiger un rapport de synthèse sur les mathématiques françaises. Lire le communiqué de presse.

Colloque on Quantum Computing

Le colloque « Recent Advances on Quantum Computing » organisé par Frédéric Magniez (IRIF) et qui s'est tenu les 17 et 18 juin au Collège de France, est désormais disponible en ligne.

Project The step towards optical computers

Simona Etinski, PhD student at IRIF is jointly in charge of one of the projects of The International Research School (IRS). In the project “The step towards optical computers”, the goal is to simulate a work of a device that is based on the laws of optics. Simona’s role, as a co-tutor in this project, is to help the students to finish their task and successfully present it at the end of the school. Watch here the video explaining the project.

Accepted paper ISSAC 2021

Sylvain Périfel and Mahsa Shirmohammadi (IRIF), Nikhil Balaji and James Worrell (University of Oxford) will present at ISSAC 2021 an article about Cyclotomic Identity Testing and Applications.

Accepted paper ICALP 2021

Thomas Colcombet and Arthur Jaquard (IRIF) will present at ICALP 2021 their paper about a complexity approach to tree algebras.

Accepted paper ICALP 2021

Antonio Casares & Thomas Colcombet (IRIF) and Nathanaël Fijalkow (Labri) will present at ICALP 2021 their research about optimal transformations of Muller conditions.

Accepted paper ICALP 2021

Claire Mathieu (IRIF), Chien-chung Huang, Mathieu Mari and Jens Vygen will present at ICALP‘2021 an article about approximating maximum integral multiflows on bounded genus graphs.

Accepted paper ICALP 2021

Sander Gribling (IRIF), Joran van Apeldoorn (Universiteit van Amsterdam), Yinan Li (Nagoya University) Harold Nieuwboer (Universiteit van Amsterdam), Michael Walter (University of Amsterdam) and Ronald de Wolf (University of Amsterdam) will present at ICALP'21 an article about quantum algorithms for matrix scaling and matrix balancing.

Prix de thèse SIF - Gilles Kahn

Appel à candidatures | Prix de thèse Gilles Kahn patronné par l'Académie des Sciences et décerné par la Société informatique de France (SIF). Ce prix a pour objectif de promouvoir les jeunes talents les plus prometteurs de l'informatique fondamentale. Date limite de dépôt des candidatures : 14 septembre 2021.

Séminaire de la chaire annuelle Informatique et sciences numériques du Collège de France

En relation avec le sujet du cours Information quantique, premières utilisations calculatoires : superposition, mesure, transformation, non-clonage, distribution quantique de clés, téléportation, Miklos Santha (IRIF) a donné un séminaire intitulé Le problème du sous-groupe caché. La rediffusion de ce séminaire (1h) est désormais disponible pour téléchargement.


Un projet de vulgarisation scientifique, financé par l’IRIF, qui a pour but de fabriquer des objets interactifs pédagogiques et ludiques pour expliquer les bases de l'ordinateur quantique ? C'est le principe du projet QuBobs pensé par Sophie Laplante (IRIF) et Lou Vettier, designer indépendante.

Offre de thèse sur la décomposition modulaire de graphes en vue de leur compression

As part of the ANR Coregraphie project, a financed PhD thesis is proposed at IRIF on the modular decomposition of graphs with a view to their compression. More details here.

Distinguished presentation at ACT 2021

Nicolas Behr (IRIF) and Joachim Kock (Universitat Autònoma de Barcelona), will present “Tracelet Hopf algebras and decomposition spaces”, selected paper for a distinguished presentation at the prestigious conference ACT 2021.

Colloque au Collège de France

Colloquium « Recent Advances on Quantum Computing » at Collège de France, June 17-18. This is a joint event between the Chaire Quantum Algorithms (2020-21) at Collège de France and the series of workshops Quantum In Paris. The goal of this colloquium is to bring together at College de France the research community in quantum computing.

Accepted paper CCC'21

Troy Lee (CQT), Tongyang Li (University of Maryland), Miklos Santha (IRIF), Shengyu Zhang (CUHK) will present at CCC 2021 the paper « On the Cut dimension of a graph ».

Accepted paper LICS'21

Claudia Faggian (IRIF) and Francesco Gavazzo (U. Bologna) will present at LICS21 a foundation for monadic rewriting, and its application to calculi with algebric effects.

Accepted paper LICS'21

Paul-André Melliès (IRIF) will present at LICS 2021 an asynchronous template game semantics where the shuffle tensor product of asynchronous games is formulated for the first time as the Gray tensor product of 2-categories, with appropriate scheduling template.

Entretien quantique - Collège de France

Invité sur la chaire annuelle Informatique et sciences numériques du Collège de France 2020-2021, le Professeur Frédéric Magniez discute de la naissance de l'écosystème de l'informatique quantique. Lisez son interview !

LICS 2021 - Accepted papers

Antoine Allioux (IRIF), Eric Finster (Cambridge University), and Matthieu Sozeau (Inria) will present at LICS 2021 a proof that types are infinity-groupoids internal to an extension of homotopy type theory allowing for the formalization of higher algebraic structures.

LICS 2021- Accepted paper

Thomas Ehrhard (IRIF) and Farzad Jafarrahmani (Université de Paris) will present at LICS2021 the first categorical semantics of Linear Logic with induction and coinduction.

Portrait de Pierre-Evariste Dagand

IRIF has the great pleasure to welcome a new research scientist (CNRS) : Pierre-Evariste Dagand, an expert in language programming. Learn more about him and his work.

CanaDAM conference 2021

Three papers coauthored by IRIF members will be presented at the CanaDAM conference 2021, May 25-28.

Parametricity and Semi-Cubical Types

Hugo Moeneclaey (IRIF) will present at LICS 2021 a construction semi-cubical models of type theory as cofree parametric models.

On the logical structure of choice and bar induction principles

Nuria Brede (University of Potsdam) and Hugo Herbelin (IRIF) will present at LICS21 a unified classification of choice and bar induction principles.

Accepted papers LAGOS'21

Two papers coauthored by IRIF members will be presented at the Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), May 17-21.

Logic in Computer Science

Ralph Sarkis (IRIF), Matteo Mio (LIP, ENS Lyon) and Valeria Vignudelli (LIP, ENS Lyon) will present at LICS2021 equational and metric reasoning tools for programs combining nondeterminism, probability and termination.

Conférence Maths en Mouvement

L'édition 2021 de Mathématiques en mouvement, organisée par la FSMP, aura lieu le mercredi 19 mai de 14h à 17h15 en visioconférence. Elle aura pour thème Maths et sport.

ICALP'21-Accepted papers

Six papers coauthored by IRIF members will be presented at the prestigious conference ICALP’21 this summer.

PGSM program of FSMP

IRIF will finance one or two additional Master scholarships in Foundations of Computer Science within the PGSM program of FSMP for female students who have completed a bachelor’s degree or the first year masters in one of the universities of the FSMP network. Apply online by May 8th.

Online Annual Meeting 3-5 May 2021

The Annual meeting of ANR-HOSIGRA, in collaboration with teams from India and China, will take place online May 3-6. The schedule of the talks is available here. Find abstracts and the zoom link here.

LICS 2021

Six papers coauthored by IRIF members will be presented at the prestigious conference LICS'21 this summer. Topics include game semantics, linear logic, categorical models, type theory and rewriting systems.

Blog binaire

Sylvain Perifel (IRIF) and Guillaume Lagarde (Université de Bordeaux) publish on the Blog Binaire the first article of a series about algorithmic complexity. The series aims be easy-to-understand and accessible to everyone.


We are happy to welcome Mirna DŽAMONJA, winner of an individual grant Marie CURIE part of the H2020 European program. Learn more about her and her work here

Stephen Wolfram

Stephen Wolfram, pioneer in the development and application of computational thinking, will be speaking on Wednesday April 28, 18:00 CET at GReTA special event co-organized by IRIF.

The ANR projet MAVeriQ will be having its second kickoff meeting on Friday March 26th. It will be starting with 4 short scientific talks: Eugene Asarin (IRIF), Loïc Helouet (IRISA), Nicolas Basset (VERIMAG), Benoît Barbot (LACL). Anybody who is interested is kindly invited to attend.

This year's PPS days will take place online on the afternoons of March 22, 23, 29 and April 1. There will be also two guest lectures on the mornings of March 23 and April 1 by Chantal Keller (LRI) and Pierre-Évariste Dagand (moving from LIP6 to IRIF).

The GDR-IM days will take place (online) from March 23rd to 26th. 2 IRIF members are participating this year: Claire Mathieu (Tuesday, March 23-9:00 am) and Michele Pagani (Wednesday, March 24-10:15 am).

Mélodie Lapointe, Simona Etinsky and Zeinab Nehaï, doctoral and post-doctoral students at IRIF took part in a Q&A session with Eva Ryckelynck (Head of administration at IRIF) and Valérie Berthé (Senior Research Scientist-CNRS). They talked about their career as women in the field of computer science.

We (IRIF) are proud to announce that we collectively finalised our Charter/Code of conduct for a secure professional environment open to diversity.


A new experimental demonstration of quantum advantage, co-authored by Iordanis Kerenidis (IRIF, CNRS), is published in Nature Communications. To learn more (in French): the CNRS press release, an article in CNRS journal, an article in L'usine nouvelle, an article in Industrie & Technologies, a radio interview of Iordanis Kerenidis on France Info.

The ANR Probabilistic Programming Semantics (PPS) meeting will take place online from Feb 16 to Feb 18, 2021 and will be joined with the 4th edition of the PIHOC workshop series and with a Dal Lago's DIAPASoN ERC project meeting. More on the program and connexion details at

Université de Paris

Three tenured positions in theoretical computer science in Paris: two associate professorships and one full professorship are open; teaching at the CS dept. of Université de Paris, research at IRIF; deadline for applications Feb. 26, 2021.

Université de Paris

Juliusz Chroboczek, Sophie Laplante and Sylvain Perifel (IRIF) are grant recipients for a project aiming to enhance the students' experience in virtual classrooms.

IRIF is associated to two projects selected under the call “Émergence en Recherche” of Université de Paris: IDiLL, co-instigated by Michele Pagani with LIPN, and SPECTRANS by Jean-Baptiste Yunès with CLILLAC-ARP and LIPADE.

French president Emmanuel Macron has presented a national plan for quantum technologies, including some aspects of quantum computing and communications. This is based on a parliamentary report co-written by Iordanis Kerenidis. More from CNRS including a special edition on the quantum revolution.

Valérie Berthé

V. Berthé (IRIF) & J. Barral spearhead the creation of 𝘎𝘋𝘙 Multifractal analysis and self-similarity as a renewal of `GDR Multifractal analysis' with a move towards symbolic dynamic systems.


Geoffroy Couteau (IRIF), Pooya Farshim (University of York), and Mohammad Mahmoody (University of Virginia) will present at ITCS 2021 a new framework for proving black-box separations in cryptography in a composable way.

Collège de France

Frédéric Magniez (IRIF CNRS member) holds the 2020–2021 chair on Computer Science at Collège de France (in partnership with Inria), where he will present a course on Quantum Algorithms starting April 7th with an Inaugural lecture on April 1st. Poster with full program.


P. Fraigniaud (IRIF), F. Le Gall (Nagoya University), H. Nishimura (Nagoya University), and A. Paz (Universität Wien) will present at ITCS 2021 a quantum approach of distributed certification, for checking the consistency of large data sets replicated at several nodes of a network.


Galène, the videconferencing server developed by Juliusz Chroboczek (IRIF), is now free and open source software. Talk and demonstration during the IRILL seminar on March 11th, 4pm.


A group of researchers from Chennai, Paris, and Uppsala, including Ahmed Bouajjani from IRIF, will publish at POPL 2021 the first decidability result for verifying concurrent programs over Persistent Memories. Another contribution of the article is a new formal model for the persistent Intel x86 architecture.

Ugo Dal Lago (Univ. Bologna), Claudia Faggian (IRIF), and Simona Ronchi Della Rocca (Univ. Torino) will present at POPL 2021 a type system to characterize probabilistic termination and (exact) expected runtime of programs in the context of higher-order probabilistic computation.

Damiano Mazza (LIPN) and Michele Pagani (IRIF) will present at POPL 2021 the first proof of the almost everywhere correctness of automatic differentiation in the context of a higher-order, Turing-complete programming language.


December 10-11, IRIF is co-organizing SOCS2020, a workshop on Species and Operads in Combinatorics and Semantics. This event will gather two very active communities in Paris area and beyond, the combinatorics and semantics communities, around a common tool: species and operads theory.

Pierre-Louis Curien

Pierre-Louis Curien (IRIF) is awarded with this year's Grand prix Inria – Académie des sciences. To learn more about Pierre-Louis Curien's contributions to theoretical computer science, read the portrayal published by Inria, and the interviews published by FSMP and La Recherche, or watch the interview by Université de Paris.

Three papers co-authored by IRIF members will be presented at POPL2021, the main conference on programming languages and programming systems. The papers' study randomized computation, including machine learning, and verification for programs over persistent memory.

Delia Kesner

Delia Kesner (IRIF) has been elected corresponding member for information sciences of the Accademia delle Scienze di Torino.

Geoffroy Couteau

A paper by G. Couteau (IRIF CNRS researcher) and D. Hartmann has been presented at the conference CRYPTO2020 and describes new, more compact constructions of non-interactive zero-knowledge proofs in elliptic curves equipped with a bilinear map.

Claire Mathieu

A paper by C. Mathieu (IRIF CNRS member) with R. Rajaraman, N. Young, and A. Yousefi will be presented at SODA2021 on dynamization policies in the competitive analysis framework for log-structured merge trees underpinning industrial NoSQL databases.

Nicolas Behr

IRIF has the great pleasure to welcome a new research scientist (CNRS): Nicolas Behr, an expert in stochastic rewriting theory.

Miklós Santha

A paper by Troy Lee, Miklós Santha (IRIF CNRS member), and Shengyu Zhang on quantum algorithms for graph problems with cut queries will be presented at SODA2021.

Geoffroy Couteau

A paper by E. Boyle, G. Couteau (IRIF CNRS researcher), N. Gilboa, Y. Ishai, L. Kohl and P. Scholl has been resented at the conference CRYPTO2020 on how to securely generate bounded amounts of correlated randomness.

Liat Peterfreund

Liat Peterfreund (former IRIF postdoc, 2019-20) is one of the recipients of the L'Oréal-Unesco award for women in science. Liat is studying the science of data processing: how to extract data, how to classify it and, above all, how to make it meaningful.


IRIF is seeking excellent candidates for about 10 postdoctoral positions in all areas of the foundations of Computer Science. Deadline for applications: Nov. 2, 2020.

Adrian Vladu

IRIF has the great pleasure to welcome a new research scientist (CNRS): Adrian Vladu, an expert in continuous optimization, which he uses to develop improved algorithms for combinatorial problems and methods for machine learning.

Preuves, Programmes et Systèmes

This year's PPS days will take place online on October 1, 8, and 15, each time between 10:20 and 12:30.


Via DIMs of Math and Infos, IRIF is one of the lab of the Paris Region Fellowship Program, a project aimed at strengthening the research capacity and international influence of Paris region, attracting excellent researcher and fostering innovation.

Mikael Rabie

IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Mikael Rabie, an expert in Distributed Computing, in particular on population protocols and distributed models on graphs.

Thomas Vidick

Thomas Vidick will give a series of lectures on Interactive proofs with quantum devices during his stay at IRIF funded by an FSMP chair, starting on Sep. 22 at IHP.

Baptiste Louf

Baptiste Louf (just graduated from IRIF) has a paper co-authored with Thomas Budzinski published in Inventiones Mathematicae that proves a conjecture of Benjamini & Curien in discrete random geometry.

Numeration - OWNS

The One World Numeration Seminar is an international online seminar on numeration systems and related topics organised by Wolfgang Steiner (IRIF). It has been well accepted by the community, and the second season starts with a talk by Bill Mance on September 1st.


Delia Kesner (IRIF) will be on the panel of a debate on the future of the conference system in theoretical computer science, and organized as a special event as part of the Online Worldwide Seminar on Logic and Semantics (OWLS). The event will take place September 2, 5pm on Zoom.

David Peleg

IRIF is very pleased to host for 4 months starting on March 2021, David Peleg, professor at the Weitzmann Institute of Science whose research focuses on algorithms, communication networks, complex and distributed systems on a chair funded by FSMP.

Thomas Vidick

IRIF is very pleased to host for 12 months starting in September 2020, Thomas Vidick, professor of computer science and mathematics at the California Institute of Technology. His research is at the interface of theoretical computer science, quantum information and cryptography. The invitation is funded by an FSMP chair together with DIENS, Inria and IRIF. Meet him in office 4024.

Iordanis Kerenidis

Iordanis Kerenidis (IRIF) was an invited speaker at International Conference on Machine Learning (ICML) in July 2020 for a talk on Quantum Machine Learning: prospects and challenges followed by a discussion with other experts in the field. Watch him online.

Enka Blanchard

Enka Blanchard, Ph.D. student at IRIF supervised by Nicolas Schabanel and Ted Selker, was awarded the PSL prize in the category “interfaces between humanities and sciences” for her Ph.D. work entitled “Usability low tech, high security”.

The members of the CS department and the laboratory IRIF of Université de Paris voted in favor of a motion requesting the withdrawal of the LPPR project.

Tommaso Petrucciani

Tommaso Petrucciani is awarded the GPL PhD Thesis Prize (Software Engineering and Programming) for his thesis“ “Polymorphic set-theoretic types for functional languages” prepared at IRIF co-supervised by Giuseppe Castagna (IRIF) and Elena Zucca (Università di Genova).
Polymorphism and set-theoretic types

A function is polymorphic when it can be applied to arguments of different types. For instance, the identity function fun x = x is polymorphic since it can be applied, say, to integers and Boolean arguments, while the successor function fun x = x+1 is not, since it can be applied only to integers. The latter function has type Int→Int, while the former has type ∀α.α→α, that is, it has type α→α for all possibles types α. The last type is a polymorphic type. Set theoretic types are types with union, intersection, and negation connectives: again fun x = x has both type Int→Int and Bool→Bool and, thus, it has the intersection type (Int→Int)∩(Bool→Bool).
Amos Korman

Amos Korman (IRIF) will give a talk for receiving the 2020 prize of innovations in distributed computing. It will be broadcast live on Tuesday, June 30, at 7-8 pm (CET). Watching the talk is free of charge, but registration is required.

Sylvain Schmitz

Sylvain Schmitz (IRIF) co-organizes the 14th International Conference on Reachability Problems (RP'20), that is planned to take place either online or at IRIF on October 19-20.


Members of IRIF organize the fifth International Conference on Formal Structures for Computation and Deduction (FSCD) and its affiliated workshops. The event was planned in Paris, due to the pandemic, it is now an online conference held from 06-29 to 07-06.

Sciences POP

Jean Krivine (IRIF) discusses how to model an epidemy with Samuel Alizon (MIVEGEC) in a video for Sciences Pop’ Saint-Denis, an association for popular education.

Amos Korman

Amos Korman (IRIF) has been awarded the 2020 Prize for Innovation in Distributed Computing. The prize will be given during the SIROCCO 2020 conference in July.

Theoretical Computer Scientists for Future

Thomas Colcombet and Hugo Férée (IRIF) together with Antoine Amarilli and Thomas Schwentick administrate the website for the TCS4F Manifesto, an initiative to reduce the carbon footprint related to Theoretical Computer Science research activities.

An online ANR-HOSIGRA 2020 meeting will be held on Tuesday May 12, 14:00-17:00 with a possibility of further discussions on the following days. If interested in joining the meeting, please contact Reza Naserasr.

Simon Mauras

IRIF PhD student Simon Mauras had a paper accepted at the EC 2020 conference, “Two-Sided Random Matching Markets: Ex-Ante Equivalence of the Deferred Acceptance Procedures”

Numeration - OWNS

The One World Numeration Seminar, a new international online seminar on numeration systems and related topics, is organised by Wolfgang Steiner (IRIF) and hosted at IRIF. It starts on May 5 with a talk by Narad Rampersad.

Claire Mathieu

Claire Mathieu (IRIF) has been interviewed by the online news site of CNRS about using graphs to devise a lockdown exit strategy.

Raphaëlle Crubillé

At ICALP'20, Raphaëlle Crubillé (IMDEA Software Institute and IRIF), with Boaz Barak and Ugo Dal Lago take a look at how higher-order cryptography could look like, giving both positive and negative results on higher-order generalizations of pseudorandomness constructions.

Thomas Colcombet (IRIF) with David Barozzini, Lorenzo Clemente and Paweł Parys (Univ Warsaw) will virtually present at ICALP'20 how to compute downward closures of safe recursion schemes, objects that give meaningful information about the behavior of higher order programs. This paper got the best paper award of ICALP/Tack-B.

Pierre Fraigniaud

Pierre Fraigniaud (IRIF) and Ami Paz (U. Vienna, Austria) will virtually present at ICALP'20 how to model distributed computing in networks in the framework of algebraic topology, where algorithms are characterized as simplicial maps between complexes.

Frédéric Magniez

In the context of quantum cloud computing, Frédéric Magniez (IRIF) with Ashwin Nayak (U. Waterloo) will introduce at ICALP'20 a fundamentally new and more efficient solution than classical ones to decide if there is inconsistency between 2 or more remote quantum databases.


Six papers coauthored by IRIF members will be presented at the prestigious conference LICS'20 this summer. Topics include the semantics of probabilistic and nondeterministic programming languages, as well as extensions of the proof-program correspondence to classical logic.


Four papers coauthored by IRIF members will be presented at the prestigious conference ICALP'20 this summer. Topics include automata, cryptography, networks, and quantum computing.

John Horton Conway

John Horton Conway passed away at 82 on 04-11 from COVID. Mathematician with an impressive spectrum of expertise, his influence on theoretical computer science is decisive from cellular automata to paving. Valérie Berthé (IRIF) wrote a note for La Recherche.
John Conway's Game of Life


The OCaml MOOC developed by Ralf Treinen, Roberto Di Cosmo and Yann Régis-Gianas from IRIF is reopened during COVID19 sheltering. Use this time at home to learn functional programming!


All seminars of IRIF are now active again through BigBlueButton, an open source solution installed on our local servers thanks to our amazing staff support. Check out our page about seminars for more information.


The first virtual workshop co-organized by a member of IRIF, Valérie Berthé, took place March 23-27 on Multidimensional Continued Fractions and Euclidean Dynamics. All talks have been recorded and are publicly accessible.

IRIF Distinguished Talks

We are delighted to host Joseph Mitchell (Stony Brook University) as part of our IRIF Distinguished Talks Series on March 20, 10:30 for a talk entitled “Approximation Algorithms for Some Geometric Packing/Covering/Routing Problems”.

PLDI 2020

Two papers co-authored by IRIF members will be presented at PLDI'20, the main conference on implementations of programming languages. The papers propose new methodologies for verifying distributed protocols and smart contracts running on top of blockchains, respectively.

IRIF will finance one or two additional Master scholarships in Foundations of Computer Science within the PGSM program of FSMP for female students who have completed a bachelor’s degree or the first year masters in one of the universities of the FSMP network. Apply by May 8th.


Sylvain Périfel from IRIF, together with Damiano Mazza and Thomas Seiller, organize the Caleidoscope Research School in Computational Complexity, to be held in Paris (postponed to 2021).

JFLA 2020

Yann Régis-Gianas (IRIF) is the vice-president of the “Journées Francophones des Langages Applicatifs” that will take place at Gruissan from the 29th of January to the 1st of February.

The ANR PPS kick-off meeting will take place from Feb 26 to Feb 28, 2020 at IRIF (Paris) and will be joined with the 3rd edition of the PIHOC workshop series initiated by Ugo Dal Lago in 2018 and with Dal Lago's DIAPASoN ERC project kick-off meeting. Register by Jan 31: registration is free but mandatory.

The ASD day of « Algorithms and discrete structures » pole will take place in room 3052 on January 27th.

Emilio J. Gallego Arias

IRIF has the great pleasure to welcome a new starting researcher (Inria): Emilio J. Gallego Arias, an expert in interactive theorem proving and the Coq proof assistant.

Report about Quantum Technologies

Iordanis Kerenidis, CNRS senior researcher (IRIF) and director of the Paris Centre for Quantum Computing, is one of the three authors of the report about Quantum Technologies requested by the French government.

Matthieu Josuat-Vergès

IRIF has the great pleasure to welcome a new research scientist (CNRS): Matthieu Josuat-Vergès, an expert in enumerative combinatorics and algebraic combinatorics.

Université de Paris

Université de Paris has opened one permanent associate professor position in Computer Science. Recruited researcher will join IRIF. Apply by April 9th, 4pm (Paris time).


Guillaume Ducoffe (Bucarest Univ. and ICI) will present at SODA’20 a result obtained with Michel Habib (IRIF) and Laurent Viennot (IRIF and Inria) showing that diameter can be computed in truly sub-quadratic time in any H-minor free graph. This extends a recent breakthrough on planar graphs.


Claire Mathieu and Simon Mauras (IRIF) will present at SODA’20 several approximation algorithms for top-list aggregation, an optimization problem from the field of information retrieval: compute the output full-ranking which is closest to a collection of input top-lists.

IRIF Distinguished Talks Series

We are delighted to host as part of our IRIF Distinguished Talks Series Martin Grohe (RWTH Aachen University) on Friday January 24, 2020, 10:30am for a talk entitled “Symmetry and Similarity”.

Institut de France

IRIF is proud to announce that Claire Mathieu, senior research scientist at IRIF, has been elected at the Académie des sciences for the section of mechanical engineering and computer science.

Société Informatique de France

Raphaëlle Crubillé (former student at IRIF)‬⁩ was awarded the Gilles Kahn 2019 prize for her PhD thesis entitled « Behavioral Distances for Probabilistic Higher-order Programs » supervised by Thomas Ehrhard (IRIF) and Ugo Dal Lago.


Two papers coauthored by IRIF members will be presented at POPL’20, the main conference on programming languages and programming systems. The papers' topics are reflecting Coq in Coq and how to differentiate higher-order programs.

Michele Pagani

Michele Pagani (IRIF), Alois Brunel (Deepomatic) and Damiano Mazza (LIPN) will present at POPL'20 an effect-free extension of the backpropagation algorithm to higher-order functional programming, allowing for a logical understanding of its dynamics thanks to linear logic.

Yann Régis-Gianas

Yann Regis-Gianas (IRIF) co-organizes at IRIF the workshop “Tezos Smart Contrat Languages and Formal Verification” on the 21 and 22 of November. Registration is free but mandatory.


What are near-term quantum computers good for? Iordanis Kerenidis (IRIF) will give a talk on 11/29 in a meeting organized by the DIM Sirteq where Google will present its recent results about quantum supremacy. Registration is free but mandatory.

IRIF hosts the annual meeting of the molecular bioinformatics research group of CNRS (GDR BIM) from 11-05 to 11-07.

Collège de France

Walter FONTANA (MedSchool Harvard) holds the annual chair of Collège de France on the theme “Life and the Computer: The Challenge of a Science of Organization”. The lectures and seminars started since the 10-24. Jean Krivine (IRIF) will give a seminar the 11-22.

Marie Kerjean

Marie Kerjean (former IRIF PhD student) is one of the recipients of the L'Oréal-Unesco award for women in science. Marie is building a bridge between logic, programming, and physics using functional analysis to model proofs, and types to understand analysis.


On December 16th, a half-day of talks aimed at a non-specialized audience will take place at IRIF in celebration of Algorithms, the research domain of Claire Mathieu, 2019 recipient of a CNRS Silver Medal. The event will conclude with a discussion of new research directions in Algorithms. Free Registration before November 30th.

Claire Mathieu

The SODA 2020 conference will include a paper by Vincent Cohen-Addad (LIP6), Frederick Mallmann-Trenn (King's College) and Claire Mathieu (IRIF) about computing with noisy data. The problem: select valuable objects in a setting where each assessment has a probability of error, using redundant assessments.

IRIF Distinguished Talks Series

Talks of the IRIF Distinguished Talks Series for the coming academic year have been scheduled. Save the dates: January 24, March 20 and June 20. Speakers will be Martin Grohe (RWTH Aachen University), Joseph Mitchell (State University of New York at Stony Brook), Simon Peyton Jones (Microsoft Research at Cambridge, England).

Sylvain Perifel

From ancient history to quantum, learn about cryptography at “Fête de la science” in an entertaining talk by Sylvain Perifel (IRIF) Friday October 11th, 11am at Amphitheater 4C, Halle aux farines.


Researchers of IRIF are participating in the “Fête de la Science”! Meet them at the University of Paris October 10-11 to better understand the first principles of computing!

Hugo Férée

IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Hugo Férée, an expert in various aspects of complexity theory, with interests in programming languages and formal proofs.

Geoffroy Couteau

IRIF has the great pleasure to welcome a new research scientist (CNRS): Geoffroy Couteau, an expert in cryptography, with a focus on secure computation protocols and zero-knowledge proofs.


Three papers coauthored by IRIF members will be presented at SODA’20, the main conference in algorithm design. Topics include the study of noisy models, aggregate rankings, and graph diameters.

Sam Van Gool

IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Sam Van Gool, an expert in algebraic and topological methods for automata, logic, and model theory.

Sylvain Schmitz

IRIF has the great pleasure to welcome a new professor (Université de Paris): Sylvain Schmitz, an expert in logic and verification, and especially in problems of astronomical computational complexity.

Valia Mitsou

IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Valia Mitsou, an expert in algorithms and complexity, particularly in structural parameterizations and fine grained complexity.

Workshop on Gradual Typing

Giuseppe Castagna (IRIF) and Jeremy Siek (Indiana) organize WGT 2020, the first ACM SIGPLAN Workshop on Gradual Typing, colocated with POPL. Submission deadline: Monday, October the 21st.
gradual typing

Gradual typing is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to gradually add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution.

From September 30th to October 21st, Leonid Libkin (University of Edinburgh) will give a series of 7 courses related to his FSMP Chair on the topic of A modern theory of database query languages each Friday 10:30-12:00 at IRIF, room 3052.

IRIF is having its back-to-work-day on October 1st. In the morning, there will be a welcome session for new PhD students, postdocs and TA, and in the afternoon a series of talks given by new faculty and CNRS members.


Giuseppe Castagna (IRIF) and his coauthors Mariangiola Dezani, Elena Giachino, and Luca Padovani (Università di Torino) will receive on October the 8th at PPDP 2019 the Most Influential Paper 10-Year Award for their paper Foundation of Session Types presented at PPDP 2009.
Session Types

Session types can be thought of as “types for protocols”, insofar as they describe all the possible sequences of interactions between services, together with the type of the information exchanged in these interactions. Programs can be checked to see if the processes they implement conform to the protocols described by a session type.

A. Balliu and D. Olivetti (former IRIF PhD students), J. Hirvonen and M. Rabie (former IRIF postdocs), with S. Brandt and J. Suomela broke an old lower bound open question on Maximal Matchings. Their paper will be presented at FOCS as Best Paper.

IRIF is seeking excellent candidates for about 10 postdoctoral positions in all areas of the Foundations of Computer Science. Deadline for applications: Nov. 3, 2019.

Patrick Dehornoy

It is with great sadness that we learnt the passing of our collegue Patrick Dehornoy on September the 4th. IRIF had the chance to count this exceptional mathematician amongst its associate members. He will be terribly missed by all his colleagues and it is a great loss for the whole scientific community.

Leonid Libkin

IRIF has the great pleasure to welcome Leonid Libkin, professor at University of Edinburgh, who is visiting for three months. His stay is financed by an FSMP chair. Leonid is an expert in data management and applications of logic in computer science. Meet him in office 4048.

Preuves, Programmes et Systèmes

The PPS days will happen in the Turing amphiteater the 2nd and 3rd of September.

A workshop on Graph Compression and Compact Representations will take place at IRIF on September 9-10. Submit your talk proposal before the 25th of August.


A scientific meeting in honor of Pierre-Louis Curien will take place at IRIF, in the amphiteater 4C, Halle aux Farines building on the 6th of September. Registration is free but mandatory.

Laboratoire IRIF: Institut de Rechecrche en Informatique Fondamentale

IRIF is celebrating the end of the academic year on the 4th of July at Amphi Pierre-Gilles de Gênes, building Condorcet with a talk at 4.00 by Emmanuelle Frenoux about computer science and the environment, and another at 5.00 by Anne Siegel about gender balance.

A summer school CIMPA entitled “Algorithmic and statistical approaches to machine learning” co-organized by Vlady Ravelomanana will take place at the University of Antananarivo from the 16th to the 25th of July 2019.

Kamil Khadiev

Kamil Khadiev from Kazan University, an expert in complexity and quantum computing, is visiting IRIF from June 10th to July 9th.

Conference CAV'19

Four papers coauthored by IRIF members will be presented at the prestigious conference CAV'19 in New York this summer. Topics include verifying weakly-consistent distributed databases, testing cache coherence protocols, and testing concurrent objects.


Mikaël Rabie (Postdoc at IRIF) will present at ICALP'19 a new problem, about distributed reconfiguration of maximal independent sets, providing an optimal algorithm to produce a reconfiguration schedule in the LOCAL model. This work, receiving Best Paper award in Track C, is a joint work with Keren Censor-Hillel from the Technion (Haifa, Israël).

Institut Universitaire de France

IRIF is proud to announce that Constantin Enea, associate professor of Université de Paris and researcher at IRIF, was appointed junior member of IUF. This appointment will allow him to develop a research project concerning rigorous engineering of distributed databases.


Claire Mathieu, Amaury Pouly and Yann Régis-Gianas from IRIF gave talks at the conference of French preparatory schools to science and engineering curriculum in May 6-10, contributing to the ongoing important changes in Computer Science education in French high-schools and higher-education systems.

Claire Mathieu from IRIF explained what algorithms are and what is their history to a national French radio broadcast show about Philosophy.


Seven papers coauthored by IRIF members will be presented at the prestigious conference ICALP'19 in Patras this summer. Topics include automata, games, graphs, quantum computing, randomized complexity, and semigroups.

Sergio Rajsbaum from Universidad Nacional Autonoma de Mexico, a world-renowned expert in the theory of distributed computing, is visiting IRIF from March 31st to May 2nd.
Distributed systems

Distributed systems are groups of networked computers, interacting with each other in order to achieve the same goal. In parallel computing, all processors have access to a shared memory to exchange information between processors. In distributed computing, information is exchanged by passing messages between the processors. Cluster of computers and peer-to-peer systems are examples of such architectures. Models of distributed systems are also used in other science, such as in biology, in order to analyze collective behaviors of autonomous entities interacting with each other by message passing.

The Spring session of Graph Theory in Paris will be held on Friday April 26 at Amphi Turing. Speakers of the event: Penny Haxell from U. Waterloo and Patrice Ossona de Mendez from CNRS.


Three papers coauthored by IRIF members will be presented at the prestigious conference LICS'19 in Vancouver this summer. Topics include sequent calculus, differential logic and probabilistic computation.

Université Paris Diderot has opened several teaching assistant positions (ATER) in Computer Science on the research topics of IRIF. Deadline to apply : May 6, 2019.


Iordanis Kerenidis (IRIF) explains what we can expect from Quantum Computing in this interview of the CNRS journal.

Ali Charara, director of INS2I at CNRS, visits IRIF on the morning of April 24th. The research conducted at IRIF will be presented as well as 6 specific scientific talks. The visit will be followed by a light buffet lunch.

Two IRIF members (Ahmed Bouajjani and Pierre Fraigniaud) will give a talk at the Workshop on Taking Stock of Distributed Computing at College de France, Friday April 12.

We are very pleased to host as part of our IRIF Distinguished Talks Series Johan Håstad (Royal Institute of Technology, Stockholm) on April 12, 10:30 for a talk entitled “Switching lemmas in the 80ies and today”.

Penny Haxell

Penny Haxell from University of Waterloo (Canada), a world wide expert in extremal combinatorics and graph theory, is visiting IRIF March 28th to May 2nd.
Extremal combinatorics

Extremal combinatorics studies how large or how small a collection of finite objects can be, if it has to satisfy certain restrictions. For instance, in an n-element set, what is the largest number of subsets of which none contains any other? The question is answered by Sperner's theorem, which gave rise to much of extremal set theory. Another kind of example: How many people can we invite to a party where among each three people there are two who know each other and two who don't know each other? Ramsey theory shows that at most five persons can attend such a party.

The ANR project DISTANCIA about graph metrics is organizing a workshop at IRIF on the 27, 28 and 29 of March in room 366A of Bâtiment Condorcet.

Ile de France

The Paris Region PhD2 program will grant 30 PhD projects on Digital Sciences and with an industrial partner. IRIF is an eligible hosting lab. Call for application is open until May, 15th 2019.

Uri Zwick

From March 20th to May 22nd, Uri Zwick (Univ. of Tel Aviv) will give a series of 7 courses related to his FSMP Chaire of Excellence on the topic of Games on Graphs and Linear Programming Abstractions each Wednesday 2:15pm - 4:15pm at IRIF, room 3052.
Linear programming

Linear programming is a technique for the optimization of a linear function, subject to linear equality and linear inequality constraints. A linear programming algorithm finds a point in the polyhedron of feasible solutions satisfying those constrains, where this function has the smallest (or largest) value. Linear programming is widely used in industries, including transportation, energy, telecommunications, and manufacturing, for diverse types of tasks such as planning, routing, scheduling, assignment, and design.

Université Paris Diderot has opened four permanent positions in Computer Science (1 professor and 3 assistant professors). Recruited researchers will join IRIF.

FSMP offers 21 PhD student positions in Maths and TCS under H2020 COFUND project MathInParis. As a member of the FSMP network, IRIF is an eligible hosting lab. Call for application is open until April, 1st 2019. Applicants must be international students, but master students already in France for less than a year are eligible.

IRIF Distinguished Talks

The Collège de France and IRIF are delighted to host as part of our IRIF Distinguished Talks Series Robert Tarjan (Princeton) on March 18, 17:00 for a talk entitled “Concurrent Connected Components”

Amaury Pouly

Amaury Pouly (IRIF) with François Fages, Guillaume Le Guludec and Olivier Bournez were awarded the prize "La Recherche": they have shown that chemical reactions, as the ones taking place in cells, can simulate Turing machines. Chemical reactions are universal computers.

Fabian Reiter

Fabian Reiter (former student at IRIF) wrote a short popularisation article in the Blog Binaire of the newspaper Le Monde. This article explains (in French) some aspects of his PhD thesis, recently awarded the Honorable Mention of the Gilles Kahn prize.

Yoav Rodeh (left) and Amos Korman (right)

In collaboration with Yoav Rodeh (Weizmann Institute of Science), Pierre Fraigniaud and Amos Korman from IRIF published a paper in the Journal of the ACM entitled “Parallel Bayesian Search with no Coordination”.


IRIF has the great pleasure to welcome Sandra Alves, assistant professor at University of Porto and expert in type-theory, rewriting, and fundamental calculi, who is visiting the IRIF until the 8th of February.

Enrica Duchi and Guillaume Chapuy (IRIF) organise February the 15th in Amphi Turing, a map day (Journée cartes) dedicated to combinatorial and probabilistic aspects of maps.

Uri Zwick

IRIF has the great pleasure to welcome Uri Zwick, professor at the Blavantik School of Computer Sience (University of Tel-Aviv), who is visiting for four months. His stay is financed by an FSMP chair. Uri is an expert in algorithms, data structures and games. Meet him in office 4048.

Carole Delporte (IRIF) will give a seminar at Collège de France as part of the annual Chair of Rachid Guerraoui (EPFL) on Distributed Algorithms, March 1.

ANR project FREDDA (FoRmal mEthods for the Design of Distributed Algorithms)

The next meeting of the ANR project FREDDA (FoRmal mEthods for the Design of Distributed Algorithms) will happen at IRIF, Monday 4th and Tuesday 5th February 2019, room 3052.


A CIMPA school on Graphs, Algorithms and Randomness is co-organized by Reza Naserasr from IRIF at Tabriz University, 15-22 June 2019. Three colleagues from IRIF, Pierre Fraigniaud, Michel Habib and Frédéric Magniez, are among the five lecturers from France.

FILOFOCS (French-Israeli Laboratory on Foundations of Computer Science), the first International Joint Unit in Israel, was just created by CNRS, Univ. Paris Diderot, Tel-Aviv Univ., Hebrew Univ. of Jerusalem and Weizmann Institute. IRIF hosts its “mirror site” in France, and Adi Rosén from IRIF is deputy director.

Pierre Fraigniaud from IRIF organizes the Workshop Complexity and Algorithms (CoA), in the framework of GdR IM, Roscoff, France, April 1-5, 2019. The objective of this workshop is to gather the French community on design and analysis of algorithms, of all forms. Deadlines: submission by 01/02/2019, registration by 02/03/2019.

Guillaume Chapuy and Enrica Duchi from IRIF coorganize with Christina Goldschmidt (Oxford) the Journées Aléa 2019, a CNRS thematic school about discrete random structures, from 03-18 to 03-22 at CIRM. Register by January 23.

Giuseppe Castagna, Victor Lanvin, Tommaso Petrucciani from IRIF present this week at POPL19 a paper coauthored with Jeremy Siek (Indiana university) about a new formal framework for gradual typing allowing a smoother and more declarative integration of gradual typing in existing programming languages.

Pole ASV: Automates, Structures, Verification

The day of the ASV pole will take place Monday January 21.

Jeremy Siek

IRIF has the great pleasure to welcome Jeremy Siek, professor at Indiana University Bloomingtom, who is visiting IRIF for five months. Jeremy is the creator of gradual typing and a world-renowed expert in typed programming languages. Meet him in office 4034a.
gradual typing

Gradual typing is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to gradually add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution.
Amaury Pouly

IRIF has the great pleasure to welcome a new researcher (CNRS), Amaury Pouly, an expert in continuous models of computations, and the analysis and verification of continuous/hybrid dynamical systems.

Christine Tasson (IRIF) will give a seminar at Collège de France as part of the lectures of Xavier Leroy (Collège de France) on Software Science, January 23.

Frédéric Magniez

Frederic Magniez (IRIF) will present at QIP 2019 a quantum distributed algorithm to compute the diameter of a quantum distributed congested network. This is the first quantum distributed algorithm that overcomes classical algorithms for this task.

Fabian Reiter

Fabian Reiter now at LSV was awarded the Honorable Mention of the Gilles Kahn prize for his PhD Distributed Automata and Logic supervised by Olivier Carton at IRIF.

Constantin Enea

Constantin Enea (IRIF) will present at POPL 2019 a methodology for specifying software modules whose operations satisfy multiple consistency levels. This work has revealed previously unknown documentation errors and bugs in Java concurrent objects.

Ahmed Bouajjani

The Alexander von Humboldt Foundation has honored Ahmed Bouajjani (IRIF) with the prestigious Carl Friedrich von Siemens Research Award, in recognition of his research contributions.

Miklos Santha and Troy Lee

Maybe you are an eager bitcoin miner? Maybe you are a fan of quantum computing too, and you wonder what will change in the mining competition when done by quantum computers? Find some answers in a paper coauthored by Miklos Santha (IRIF) to be presented at ITCS’19.

Hugues Fauconnier (IRIF) will give a seminar at Collège de France as part of the annual Chair of Rachid Guerraoui (EPFL) on Distributed Algorithms, December 21.

Matthieu Sozeau (IRIF) will give a seminar at Collège de France as part of the lectures of Xavier Leroy (Collège de France) on Software Science, December 12.

Constantin Enea from IRIF organizes with Ruzica Piskac (Yale University), the 20th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2019). The conference is preceded by a winter school on formal methods.


Two papers coauthored by IRIF members will be presented at ITCS’19, a prestigious conference to promote research that carries a strong and innovative conceptual message in TCS. Topics include communication complexity and quantum dueling algorithms.


Two papers coauthored by IRIF members will be presented at QIP’19, the main conference for theoretical quantum information research. Topics include efficient quantum algorithms for both algebraic and distributed problems.


One paper coauthored by Laurent Feuilloley while he was PhD student at IRIF will be presented at SODA’19, the main conference in algorithm design. The paper provides lower bounds for the fundamental problem of text indexing with mismatches and differences using the Strong Exponential Time Hypothesis.

Mahsa Shirmohammad

IRIF has the great pleasure to welcome Mahsa Shirmohammadi, researcher scientist (CNRS) from LIS, who is visiting IRIF for six months and who is an expert in the analysis and verification of timed, counter and probabilistic systems.


Four papers coauthored by IRIF members will be presented at POPL’19, the main conference on programming languages and programming systems. The papers' topics are game semantics, proof theory, gradual typing, and consistency for concurrent computations.
Games, gradual typing, proofs, consistency

Games are mathematical objects used for modeling situations in which several participants/players interact, and each of them aims at fulfilling a personal goal. Real games such as chess or go are cases in which there are two players which are opponents. Games occur in computer science for modeling the logical duality between conjunction and disjunctions, or for defining particular families of complexity classes. Games appear in verification for describing how a system has to react to the environment (the opponent) in order to perform what it has been designed for.
Gradual typing is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to gradually add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution.
Proof theory is the branch of mathematical logic that studies proofs as mathematical objects. In particular, proof are syntactic constructions built from axioms and inference rules. Relevant to computer science are the studies of computational and complexity aspects of proofs.
Memory consistency models characterize the effect of concurrent invocations to a library implementing a shared state, e.g., a queue or a key-value map. Strong consistency means that the results of concurrently-executed invocations match the results of some serial execution of those same invocations. Since strong consistency carries a significant penalty on performance, modern implementations provide weaker guarantees known as weak consistency models, e.g., eventual or causal consistency.


IRIF and PCQC are partners in the EU Flagship project Quantum Internet Alliance (QIA) and in charge of delivering the QIA's blueprint for the future of quantum communications. The EU selected nineteen research projects, and ten of them are based on French teams.

The first meeting of the French-Chinese research project Verification Interaction Proof will take place in Paris at IRIF on November 19-24. Registration is free but mandatory.

Distinguished Talk

We are delighted to host as part of our IRIF Distinguished Talks Series Maurice Helihy (Brown University) on Nov. 16, 10:30 for a talk entitled “Atomic Cross-Chain Swaps”.


The last plenary meeting of GDRI Logique Linéaire takes place at IRIF, December 3-5. The program consists of talks given by members of the GDRI.

Graph Theory in Paris

The first session of a series of seminars Graph Theory in Paris will be hosted by IRIF. There will be two seminars by Monique Laurent and Lex Schrijver on November 23, at 2pm, in Amphi Turing of Sophie Germain building.


Amélie Gheerbrand and Cristina Sirangelo from IRIF co-organize with L. Libkin, L. Segoufin, and P. Senellart, the 2019 Spring School on Theoretical Computer Science (EPIT) on Databases, Logic and Automata, to happen the 7-12 April 2019 in Marseille. Preregistration before 13 January 2019.

The Journées PPS 2018 will take place on Thursday 8 and Friday 9 November, room 3052, building Sophie Germain.

Pierluigi Crescenzi

IRIF has the great pleasure to welcome a new professor (Paris Diderot): Pierluigi Crescenzi, an expert in graph algorithms, particularly in the analysis of real-world complex networks.

Claire Mathieu

IRIF has the great pleasure to welcome a new research scientist (CNRS): Claire Mathieu, an expert in algorithms, particularly the design of approximation schemes for NP-hard combinatorial.

Adrien Guatto

IRIF has the great pleasure to welcome a new assistant professor (Paris Diderot): Adrien Guatto, an expert in synchronous languages, typed functional programming, and categorical semantics.

Daniela Petrisan

IRIF has the great pleasure to welcome a new assistant professor (Paris Diderot): Daniela Petrisan, an expert in categories, co-algebra and automata.

ICFP: International Conference On Functional Programming

The paper “Equivalences for Free : Univalent Parametricity for Effective Transport” of Matthieu Sozeau (IRIF), with his coauthors Nicolas Tabareau and Eric Tanter, has been selected as a distinguished paper of the ICFP conference.


On October 8-11 IRIF organizes a joint meeting of 3 projects which are closely related: GDRI-LL, CRECOGI, and ELICA. Everybody is welcome to attend.

Maths en ville

Jean Krivine (researcher at IRIF) will lead a public debate about Artificial Intelligence at the “Festival Maths en Ville” of Saint-Denis. It will take place on the 11/10/2018 at the theater “L'écran”, starting at 19.30.

Jean-Éric Pin

Jean-Eric Pin, CNRS senior researcher at IRIF, is awarded the Arto Salomaa prize for his outstanding contribution to the field of Automata Theory.

IRIF is having its back-to-work-day on October 15th. In the morning, there will be a PhD student session, and in the afternoon a series of talks given by new faculty and CNRS members.


IRIF is seeking excellent candidates for about 10 postdoctoral positions in all areas of the Foundations of Computer Science.

Software Heritage

In an article of October of Communications of the ACM, Jean-François Abramatic, Roberto Di Cosmo (IRIF) and Stefano Zacchiroli (IRIF) explain the mission of the Software Heritage project.

WENDY: Workshop on emergent algorithms

IRIF co-organizes the Workshop on Emergent Algorithms and Network Dynamics (Wendy) that will take place at Institut Henri-Poincaré in Paris on October 10-11, 2018. Registration is free but mandatory.

COmplexité et Algorithmes

The October 2, IRIF organizes the next Annual workshop of the French Working Group on Complexity and Algorithms (CoA). This year, the workshop will consist of a series of introductory and survey talks about various hot topics in algorithms, including Blockchains, Machine Learning, Sum-of-Square, etc.


The EU QuantAlgo project workshop will be held in Paris at IRIF September 25-28, 2018. This is a joint workshop with the IRIF-IQC Cooperation project between CNRS and U. Waterloo. QuantAlgo project aims to combine research on the fundamentals of quantum algorithms with the development of new applications.

The DUALL project of the ERC

IRIF organizes the workshop Quantifiers and duality that will take place at Amphi Turing (building Sophie Germain, University Paris Diderot) on the 2018/09/11. Registration is free but mandatory.

FILOFOCS: Frech-Israeli-workshop on foundations of Computer Science

IRIF organizes the 7th FILOFOCS (French-Israeli Laboratory on Foundations of Computer Science) workshop which will be held at the institut Henri Poincaré (IHP), on 3-5 October, 2018. A preliminary list of speakers in now available and registration (mandatory, but free) is now open.


At the occasion of the retirement of Michel Habib and in celebration of his achievements, IRIF organizes a two-day conference “40 années d'algorithmique de graphes”, 11-12 Oct, Amphi Turing (Sophie Germain, Univ. Paris Diderot). Free mandatory registration.


IRIF organizes the 59th IEEE Symposium on Foundations of Computer Science (FOCS 2018) on October 7-9, 2018. FOCS is a leading annual conference in Theoretical Computer Science, and has served in the last 60 years as a venue for announcing the major scientific advances in the field. The list of accepted papers is now available, and the registration is now open (deadline for early rate: September 9, 2018).


Mihaela Sighireanu (IRIF) is organizing the second edition of SL-COMP, a competition of solvers for separation logic. The final results will be presented at ADSL 2018, a workshop of FLOC2018, which will take place in Oxford on the 13.07.18.
separation logic

Separation logic is a language for describing properties and reasoning about programs that use mutable data structures (i.e. memory cells and pointers). Separation logic has a special support for local reasoning, which is the ability to use and compose properties that involve a subset of the data configuration only: it separates the relevant portion of the data structure from the irrelevant one. Local reasoning gives more compact proofs and specifications for imperative programs than with prior formalisms. Furthermore, it helps with the scalability of proofs done in automatic and semi-automatic verification and program analysis tools.

Mihaela Sighireanu (IRIF) is co-chair of the 18th International Workshop on Automated Verification of Critical Systems (AVOCS) which will take place in Oxford from 18.07.18 to 19.07.18 as part of FLOC2018.


Raphaëlle Crubillé (PhD student IRIF) will present at LICS 2018 an analytic account of the discrete probabilities fragment of a denotational model for higher-order programming with general probabilities, hopefully a first step towards proving that this model is fully abstract.
fully abstract

The quest for a fully abstract model for the contextual equivalence of PCF, a paradigmatic functional language, has been influential in the area of programming languages semantics. A model is fully abstract if it is both sound and complete. A denotational model is complete for a given notion of equivalence between programs if equivalent programs have the same denotation, some mathematical object they are mapped to; it is sound if programs having the same denotation are equivalent.

Berenice Delcroix-Oger (IRIF) participated to the annual festival Salon Culture & Jeux Mathématiques 2018. On the following video (1:50), she presents a funny game where mathematics help you perform magic tricks!

Amina Doumane

Amina Doumane (former PhD student at IRIF, now at LIP) was awarded the Ackermann prize of EACSL for her PhD thesis entitled On the infinitary proof theory of logics with fixed points.

IRIF Distinguished Talks

We are delighted to host as part of our IRIF Distinguished Talks Series Christos Papadimitriou (Columbia University) on July 13, 10:30 for a talk entitled “A computer scientist thinks about the Brain”.

Softare heritage

Today Roberto Di Cosmo (professor at IRIF) with a ceremony at UNESCO opened to the public the archives of Softwareheritage.org, a worldwide initiative to create a universal library of computer programme source codes since the dawn of the digital age.


Delia Kesner (IRIF) and Matthieu Sozeau (IRIF) will both give invited talks entitled “Multi Types for Higher-Order languages” and “The Predicative, Polymorphic Calculus of Cumulative Inductive Constructions and its implementation” at TYPES 2018, held in Braga (Portugal), June 18-21.

Collège de France

Claire Mathieu (IRIF associate member) organizes a 1-day colloquium on Approximation algorithms and networks at Collège de France on June 7. This is part of the Chair in Informatics and Computational Sciences at College de France in association with INRIA.
approximation algorithm

The approximation algorithms are algorithms that produce a solution that approximates the best possible solution of an optimization problem. While finding the optimal solution of practical problems is often infeasible, an approximation algorithm usually produces its solution in an efficient way and provides formal guarantees about the quality of the approximation. An example of such a problem is the so-called “traveling salesman problem” which consists in finding among all possible itineraries the shortest route that allows a salesman to visit a given set of cities and come back home.

Adi Rosén (IRIF) will give a talk during a 1-day colloquium at Collège de France as part of the annual Chair of Claire Mathieu (IRIF associate member) on Algorithms, June 7.

Logic in Computer Science

Paul-André Melliès (IRIF) will present at LICS 2018 his work on ribbon tensorial logic, a primary logic designed to reveal the secret topology of reasoning. This is the first time that logical proofs are faithfully translated into topological tangles using functorial knot theory.
knot theory

Knot theory studies mathematical knots. These are like the usual shoelaces and rope knots but with the difference that the ends of the string are joined together so that it cannot be undone. Of particular interest is the study of when two knots are equivalent, that is when one can be transformed into the other without cutting the string or passing the string through itself. The theory has applications in physics, biology, chemistry, and computer science. For instance, the security of some quantum money relies on the assumption that given two different looking but equivalent knots, it is difficult to explicitly find a transformation that takes one to the other.
Tous femmes du numérique !

« Tous femmes de numérique ! » Après leur rencontre avec 4 informaticiennes de l’IRIF, 14 lycéennes du Lycée Jules Ferry ont expliqué à leurs camarades l’exposition permanente du Palais de la découverte sur l’informatique et les sciences du numérique le 29/05.

Logic in Computer Science

Marie Kerjean (PhD student IRIF) will present at LICS 2018 a logical account for linear partial differential equations. With this work, she unveils a bridge between mathematical physics and proof theory, paving the way for exciting and mutually beneficial transfers of techniques.

A sequent represents a theorem by a sequence of hypotheses and the sequence of possible theses they imply. This formalism underlines a symmetry hypotheses/theses ruled by negation and is used in sequent calculus to formalise proofs and to study their properties.
Logic in Computer Science

Pierre Vial (IRIF) will present at LiCS 2018 an excerpt of his PhD work at IRIF proving that every lambda-term has an infinite linear representation in the infinitary relational model. This work pioneers a technique that allows giving a semantic even to unproductive programs.

A part of a program is unproductive if it performs an infinite number of computing steps without any interaction with the rest of the program or external devices. Unproductive code is basically useless, and may even be unsafe, and detecting parts of code that are unproductive is important to improve software quality.

Amos Korman (IRIF) Amos Korman is co-chairing, and organizing the 6th Workshop on Biological Distributed Algorithms, to be held in London in July, the 23rd.
biological algorithm

Biological algorithm is a term used to describe the biological processes from an algorithmic, or computer scientific, perspective. It concerns questions such as what are the algorithmic challenges faced by the biological organism, and what are the algorithmic principals used in order to overcome these challenges. For example, when a group of ants finds a large piece of food and needs to decide its navigation rout back to the nest, what are the benefits and pitfalls of noise in their communication?
Institue de France

Miklos Santha (IRIF) participates to the conference-debate Calcul, communication, simulation et métrologie quantiques : des principes aux réalisations concrètes organized by Académie des sciences at the Institut de France on May 15.

Institut Universitaire de France

IRIF is proud to announce that Delia Kesner, professor of University Paris Diderot and researcher at IRIF, was appointed senior member of IUF.

Logic in Computer Science

Six papers coauthored by IRIF members will be presented at the prestigious conference LICS'18 in Oxford this summer. Topics range from λ-calculus, to Separation Logic…

Research at Google

Victor Lanvin (PhD student of Giuseppe Castagna, IRIF) is awarded the Google PhD fellowship! Through the FSMP, Google will give a significant support to Victor's research work on gradual typing.
gradual typing

Gradual typing is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to gradually add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution.
Numeration 2018

The conference Numeration 2018 will be held on May 22-25 at the University Paris Diderot, and is organized by Valérie Berthé, Christiane Frougny and Wolfgang Steiner from IRIF.

Agence Nationale pour le Recherche

The next meeting of the ANR project DESCARTES, aiming at defining a modular approach for distributed computing, will take place at IRIF on March 28, 2018. Scientific talks are public.

ANR Delta

The next meeting of the ANR project DELTA, conducting research about the new challenges in Logic, Automata and Transducers, will take place at University Paris Diderot from 2018/03/26 to 2018/03/28. Scientific talks are public.

An automaton is a construct made of states designed to determine if a sequence of inputs should be accepted or rejected. It starts from initial state and when it receives a new input it moves to another state according to the way it was programmed. If at the end of all inputs the automaton is in a state designated as final, then the sequence of inputs is accepted, otherwise it is rejected.
The Kappa platform for rule-based modeling

“The Kappa platform for rule-based modeling”, a collaboration between Jean Krivine (IRIF) and researchers from Harvard University, ENS and Santa Cruz University will be presented at ISMB2018.

IRIF Distinguished Talk

In the scope of the IRIF Distinguished Talks Series Monika Henzinger (University of Vienna) will give on April 13 a talk on “The state of the art in dynamic graph algorithms”.

Algorithm: an algorithm is the formal description of a procedure that is used to solve a class of problems. The description consists in a sequence (of finite length) of operations that are interpreted unambiguously by who/what is executing the algorithm. Every algorithm can be directly executed or simulated by any Turing-complete system.

Adrian Kosowski (IRIF), together with Bartek Dudek (University of Wroclaw), will present at STOC 2018 a new protocol for spreading information in a population. This is the first time that methods of oscillatory dynamics are used to solve a basic task of information dissemination.
information dissemination

Information dissemination is the process by which a piece of information is propagated in a distributed system through direct communications from node to node. Rumor spreading between humans or broadcasting in a network are two typical examples. Information propagation is a basic building block of many distributed algorithms and its analysis is often critical in understanding their complexity.
Fondation Sciences Mathématiques de Paris

FSMP offers 20 PhD student positions in Maths and TCS under H2020 COFUND project MathInParis. As a member of the FSMP network, IRIF is an eligible hosting lab. Call for application is open until April, 1st 2018. Applicants must be international students, but master students already in France for less than a year are eligible.

Constantin Enea (IRIF) is an organizer of the 2018 edition of the EPIT research school, on the subject of software verification, to he held in Aussois on May 7-11 2018.


Peter Habermehl (IRIF) and Benedikt Bollig (LSV, ENS Paris-Saclay) organize the research school MOVEP (Modelling and Verification of Parallel Processes), on July 16-20 in Cachan.

Université Paris 7 - Denis Diderot

Université Paris Diderot has opened three permanent positions in Computer Science (1 professor on Graph and applications, 1 assistant professor on Software Science, 1 assistant professor on Data Science). Recruited researchers will join IRIF.

Palais de la Découverte

Laurent Viennot (IRIF, Inria) is Scientific Curator of the exhibition Informatique et sciences du numérique, at Palais de la découverte, starting March 13, 2018.

Amina Doumane

Amina Doumane, now at LIP, was awarded the “La Recherche” prize in the Computer Science category for her paper entitled Constructive Completeness for the linear-time mu-calculus, a work accomplished during her PhD at IRIF and that appeared in the proceedings of LICS’17.


The first on-the-fly quantum money transaction was implemented by researchers in Paris, including Iordanis Kerenidis. ​Quantum ​money is provably unforgeable​ due to the no-cloning property of quantum information.​
quantum information

Quantum Information is the information stored in a quantum system. A quantum system is composed of one or many qubits: the fundamental unit of quantum information. A qubit is a 2-dimensional vector. The basis encodes two classical values of a bit. Quantum information, i.e. Von Neuman entropy, is the analogous of Shannon entropy for classical information, and it is often used to measure physical properties of a quantum system, like the entanglement.

The international French and Argentina CNRS laboratory called INFINIS lead by Delia Kesner (IRIF) and Sergio Yovine (CONICET) is presented in the CNRS Rio newsletter.

Maurice Nivat

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

Agence Nationale pour le Recherche

January the 10th 2018, this is the kick-off meeting of the ANR project FREDDA (FoRmal mEthods for the Design of Distributed Algorithms).

Innovations in Theoretical Computer Science

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.

Convention Industrielle de Formation par la Recherche

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.

Société Informatique de France

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.

Société Informatique de France

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.

Maurice Nivat

Scientific Day in memory of Maurice Nivat, professor at Paris Diderot University and a pionneer of theoretical computer science in France and in the world, who passed away on September the 21st, 2017.


Back-to-work day of the “Automata, Structures, and Verification” pole, which gathers the research groups Automata and applications and Modelling and verification on November 25, 2017.


6th French-Israeli Workshop on Foundations of Computer Science on November 22-23, 2017 at Tel-Aviv University, Israel.


2-day workshop on December 7-8: Closing workshop of ANR project on Restricted Data Access Models and 1st IRIF-IQC Workshop on Quantum Information Processing (CNRS bilateral collaboration).


IRIF newcomers Day on November 6, 2017 at Amphi Turing

Pierre Fraigniaud (IRIF) will give a seminar at Collège de France as part of the annual Chair of Claire Mathieu (IRIF associate member) on Algorithms, November 18.


Back-to-work day of the “Proofs, programs and systems” pole on October 12-13, 2017 at room 3052.

ACM-SIAM event

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 Algorithm (SODA 2018).


Two papers coauthored by IRIF members will be presented at SODA’18, the main conference in algorithm design. Topics include the resolution of a 20-year old conjecture related to Lempel-Ziv, and a new approximation algorithm for recognizing Dyck languages.

Claire Mathieu (IRIF associate member) holds the Chair in Informatics and Computational Sciences at College de France in association with Inria for the academic year 2017-18.

Bérénice Oger

IRIF has the great pleasure to welcome a new assistant professor: Bérénice Delcroix-Oger, an expert in combinatorics and computational algebra.

ANR project MealyM

Closing workshop of ANR project MealyM on July 10-13, 2017 at Amphi Turing.

Victor Lanvin

Victor Lanvin is awarded the first prize for the ACM Student Research Competition Grand Finals, undergraduate category. The prize will be presented on June the 24th at the Turing Award Cerimony in San Francisco.

European Research Council

The 5-year ERC project CombiTop of Guillaume Chapuy has started on March 1st, 2017. The purpose of this project is to use the ubiquitous nature of certain combinatorial topological objects called maps in order to unveil deep connections between several areas of mathematics.

Le Monde

Amos Korman has been interviewed by Le Monde for his recent results on ants with several co-autors at IRIF.

Principle of Programming Languages 2017, Paris

IRIF organizes the 44th ACM Symposium on Principles of Programming Languages (POPL 2017), Jussieu, Paris, January 15-21, 2017.

(These news are displayed by date of creation)