## All the past news

*25.11.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

https://typecaseunion.github.io/.

*25.11.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.

*24.11.2021*

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

*8.11.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.

*8.11.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*.

*4.11.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.

*29.10.2021*

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.

*25.10.2021*

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.

*19.10.2021*

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.

*7.10.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.

*29.9.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.

*27.9.2021*

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.

*14.9.2021*

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.

*7.9.2021*

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

*3.9.2021*

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.

*3.9.2021*

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.

*3.9.2021*

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.

*3.9.2021*

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.

*3.9.2021*

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

*1.9.2021*

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

*30.8.2021*

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.

*27.8.2021*

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.

*26.8.2021*

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.

*24.8.2021*

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

*20.8.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”.

*26.7.2021*

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.

*19.7.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.

*19.7.2021*

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.

*19.7.2021*

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.

*8.7.2021*

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

*8.7.2021*

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

*7.7.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**.

*30.6.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**.

*29.6.2021*

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

*28.6.2021*

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.

*21.6.2021*

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.

*18.6.2021*

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.

*17.6.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.

*16.6.2021*

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.

*14.6.2021*

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** ».

*9.6.2021*

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.

*9.6.2021*

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.

*8.6.2021*

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 !

*2.6.2021*

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

*2.6.2021*

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.

*26.5.2021*

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.

*25.5.2021*

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

*21.5.2021*

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

*21.5.2021*

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

*19.5.2021*

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

*18.5.2021*

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.

*10.5.2021*

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

*10.5.2021*

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.

*29.4.2021*

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

*29.4.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.

*23.4.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.

*22.4.2021*

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.

*9.4.2021*

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**

*7.4.2021*

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.

*26.3.2021*

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.

*20.3.2021*

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

*12.3.2021*

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

*9.3.2021*

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.

*23.2.2021*

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

*18.2.2021*

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.

*10.2.2021*

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

*29.1.2021*

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

*29.1.2021*

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

*22.1.2021*

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.

*22.1.2021*

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.

*15.1.2021*

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.

*5.1.2021*

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.

*4.1.2021*

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.

*4.1.2021*

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.

*23.12.2020*

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

*22.12.2020*

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.

*22.12.2020*

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.

*21.12.2020*

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.

*4.12.2020*

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

*25.11.2020*

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.

*20.11.2020*

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

*20.11.2020*

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

*6.11.2020*

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.

*6.11.2020*

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.

*2.11.2020*

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

*21.10.2020*

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.

*21.10.2020*

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.

*15.10.2020*

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

*2.10.2020*

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

*1.10.2020*

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.

*30.9.2020*

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

*21.9.2020*

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.

*15.9.2020*

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.

*11.9.2020*

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

*4.9.2020*

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.

*1.9.2020*

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

*28.8.2020*

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

*18.8.2020*

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.

*18.8.2020*

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

*18.8.2020*

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

*16.7.2020*

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

*6.7.2020*

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

*25.6.2020*

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

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

*22.6.2020*

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.

*22.6.2020*

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

*15.6.2020*

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

*22.5.2020*

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.

*20.5.2020*

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.

*11.5.2020*

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”

*11.5.2020*

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.

*11.5.2020*

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.

*30.4.2020*

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

*27.4.2020*

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.

*27.4.2020*

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

*23.4.2020*

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.

*23.4.2020*

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

*23.4.2020*

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.

*20.4.2020*

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

*17.4.2020*

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

*15.4.2020*

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

*7.4.2020*

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.

*7.4.2020*

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!

*7.4.2020*

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

*5.3.2020*

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

*27.2.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.

*7.2.2020*

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

*6.2.2020*

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

*30.1.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**.

*27.1.2020*

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.

*21.1.2020*

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

*15.1.2020*

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.

*13.1.2020*

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.

*10.1.2020*

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

*10.1.2020*

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

*7.1.2020*

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.

*7.1.2020*

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.

*6.1.2020*

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

*23.12.2019*

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.

*13.12.2019*

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.

*11.12.2019*

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

*10.12.2019*

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.

*20.11.2019*

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.

*7.11.2019*

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

*1.11.2019*

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

*29.10.2019*

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

*23.10.2019*

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.

*16.10.2019*

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.

*8.10.2019*

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.

*8.10.2019*

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

*8.10.2019*

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!

*8.10.2019*

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.

*2.10.2019*

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.

*1.10.2019*

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.

*25.9.2019*

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.

*25.9.2019*

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

*24.9.2019*

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.

*24.9.2019*

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.

*23.9.2019*

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.

*18.9.2019*

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

*17.9.2019*

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.

*17.9.2019*

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.

*11.9.2019*

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

*10.9.2019*

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

*6.9.2019*

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.

*3.9.2019*

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

*14.7.2019*

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

*14.7.2019*

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

*28.6.2019*

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.

*21.6.2019*

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

*11.6.2019*

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

*30.5.2019*

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

*25.5.2019*

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

*10.5.2019*

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.

*9.5.2019*

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.

*7.5.2019*

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

*26.4.2019*

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

*23.4.2019*

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.

*23.4.2019*

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.

*19.4.2019*

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

*19.4.2019*

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

*19.4.2019*

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

*16.4.2019*

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.

*8.4.2019*

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

*8.4.2019*

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*”.

*5.4.2019*

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.

*26.3.2019*

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.

*17.3.2019*

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

*15.3.2019*

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

*14.3.2019*

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

*14.3.2019*

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.

*5.3.2019*

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”

*19.2.2019*

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.

*15.2.2019*

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.

*15.2.2019*

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

*4.2.2019*

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.

*1.2.2019*

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.

*1.2.2019*

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

*1.2.2019*

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.

*30.1.2019*

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.

*23.1.2019*

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.

*23.1.2019*

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.

*17.1.2019*

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.

*17.1.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**.

*16.1.2019*

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.

*10.1.2019*

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

*9.1.2019*

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.

*8.1.2019*

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.

*1.1.2019*

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

*21.12.2018*

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.

*19.12.2018*

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.

*13.12.2018*

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.

*9.12.2018*

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.

*3.12.2018*

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.

*1.12.2018*

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

*1.12.2018*

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

*29.11.2018*

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.

*21.11.2018*

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.

*20.11.2018*

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.

*20.11.2018*

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.

*19.11.2018*

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.

*17.11.2018*

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

*12.11.2018*

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

*10.11.2018*

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.

*10.11.2018*

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

*10.11.2018*

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.

*9.11.2018*

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.

*5.11.2018*

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

*5.11.2018*

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

*12.10.2018*

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.

*12.10.2018*

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.

*12.10.2018*

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.

*10.10.2018*

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

*9.10.2018*

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.

*8.10.2018*

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.

*8.10.2018*

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.

*7.10.2018*

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

*7.10.2018*

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.

*5.10.2018*

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

*4.10.2018*

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.

*15.9.2018*

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.

*14.9.2018*

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.

*11.9.2018*

Back-to-work day of the "Algorithms and discrete structures" pole, which gathers the research groups Algorithms and complexity, Combinatorics, Complex Systems, Networks, and Distributed Computing and Theory and algorithmics of graphs
on September 11, 2018, room 3059, 9h30-16h15.

*7.9.2018*

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.

*4.9.2018*

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.

*9.8.2018*

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.

*1.8.2018*

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.

*29.7.2018*

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

*29.7.2018*

Ludovic Patey was awarded the Prix Thiessé de Rosemont / Demassieux for his PhD thesis « Les mathématiques à rebours de théorèmes de type Ramsey », supervised by Laurent Bienvenu and Hugo Herbelin.

*10.7.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**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.

*6.7.2018*

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.

*29.6.2018*

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.

*27.6.2018*

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!

*15.6.2018*

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.

*6.6.2018*

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.

*6.6.2018*

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”*.

*6.6.2018*

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.

*1.6.2018*

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.

*1.6.2018*

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

*31.5.2018*

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.

*30.5.2018*

**« 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.

*25.5.2018*

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.

*21.5.2018*

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.

*11.5.2018*

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

*4.5.2018*

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

*27.4.2018*

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

*23.4.2018*

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…

*6.4.2018*

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.

*3.4.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.

*21.3.2018*

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.

*21.3.2018*

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.

*21.3.2018*

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

*8.3.2018*

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”*.

*2.3.2018*

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.

*27.2.2018*

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

*27.2.2018*

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.

*7.2.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.

*5.2.2018*

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.

*4.2.2018*

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

*2.2.2018*

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.

*1.2.2018*

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.

*27.1.2018*

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.

*18.1.2018*

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.

*11.1.2018*

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

*5.1.2018*

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

*19.12.2017*

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

*29.11.2017*

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

*29.11.2017*

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

*27.11.2017*

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.

*25.11.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.

*22.11.2017*

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

*15.11.2017*

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

*1.11.2017*

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

*10.10.2017*

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

*6.10.2017*

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

*1.10.2017*

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.

*1.9.2017*

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.

*1.9.2017*

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

*15.6.2017*

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.

*1.3.2017*

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.

*30.1.2017*

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

(These news are displayed by date of creation)