Institut de Recherche en Informatique Fondamentale (IRIF)


image/svg+xml

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui héberge une équipe-projet Inria.

Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques.

L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), cinq sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences.

Accepted paper FOCS 2021

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.

hpcqs project

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

conference-75ans-fabrice-kordon

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

Accepted papers POPL 2022

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.

visiteur-serge-massar

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

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

Portrait Matej Stehlik

29.11.2021
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 POPL 2022

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


(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

One world numeration seminar
Mardi 18 janvier 2022, 14 heures 30, Online
Agamemnon Zafeiropoulos (NTNU) The order of magnitude of Sudler products

Given an irrational $\alpha \in [0,1] \smallsetminus \mathbb{Q}$, we define the corresponding Sudler product by $$ P_N(\alpha) = \prod_{n=1}^{N}2|\sin (\pi n \alpha)|. $$ In joint work with C. Aistleitner and N. Technau, we show that when $\alpha = [0;b,b,b…]$ is a quadratic irrational with all partial quotients in its continued fraction expansion equal to some integer b, the following hold:
- If $b\leq 5$, then $\liminf_{N\to \infty}P_N(\alpha) >0$ and $\limsup_{N\to \infty} P_N(\alpha)/N < \infty$.
- If $b\geq 6$, then $\liminf_{N\to \infty}P_N(\alpha) = 0$ and $\limsup_{N\to \infty} P_N(\alpha)/N = \infty$.
We also present an analogue of the previous result for arbitrary quadratic irrationals (joint work with S. Grepstad and M. Neumueller).

Combinatoire énumérative et analytique
Jeudi 20 janvier 2022, 14 heures, Salle 3052 et sur zoom
Noémie Cartier (Université de Paris-Saclay) Lattice properties of acyclic pipe dreams

A pipe dream is a collection of pipes that trace the values of a permutation when passing through a sorting network. By choosing the sorting network and the permutation carefully, the set of reduced pipe dreams gives a realization of the Tamari lattice, a famous lattice quotient of the weak order. The talk will present a generalization of this result: if our sorting network respects a few specific properties, the set of reduced and acyclic pipe dreams of a permutation is a lattice quotient of an interval of the weak order.

Preuves, programmes et systèmes
Jeudi 20 janvier 2022, 10 heures 15, Virtual room at link
Bruno Dinis (Universidade de Lisboa) Functional interpretations and applications

Functional interpretations are maps of formulas from the language of one theory into the language of another theory, in such a way that provability is preserved. These interpretations typically replace logical relations by functional relations. Functional interpretations have many uses, such as relative consistency results, conservation results, and extraction of computational content from proofs as is the case in the so-called proof mining program.

I will present several recent functional interpretations and some results that come from these interpretations. I will also give examples of application of functional interpretations, in the spirit of the proof mining program.

Automates
Vendredi 21 janvier 2022, 14 heures 30, Salle 3052
Victor Marsault Demonstration of Awali 2.1, a library for weighted automata and transducers.

Awali is a software suite for computing with finite weighted automata and transducers with any number of tapes. Many algorithms are implemented including most of the classical ones. Automata and transducers may be weighted over a classical number sets (N,Z,Q,R,C,Z/nZ) but also over several other weightsets (such as the tropical semirings).

Awali may be accessed in C++ (awalidyn, or directly using templates) or in Python (awalipy). Awali can also be used interactively from its command-line interface (Cora) or using awalipy together with Jupyter, a top-level Python interpreter.

Awali may be downloaded from http://vaucanson-project.org/Awali/2.1/ and I'll be happy to address possible installation issues after the presentation.

Algorithmes et complexité
Mardi 25 janvier 2022, 14 heures, 3052
Simona Etinski (INRIA / IRIF) Latest challenges in post-quantum cryptography

In 2016, the National Institute of Standards and Technology (NIST) announced a call for standardization (also known as “NIST competition”) of post-quantum cryptographic protocols, i.e., cryptographic protocols considered to be resistant to quantum attacks. NIST was mainly interested in two types of protocols: digital signatures and encryption/key-establishment schemes. The fourth and final round of this competition is about to start, and once it is finished, the most efficient and thoroughly analyzed protocols will be standardized.

In this talk, we focus on the proposal for a digital signature. It is based upon a problem from coding theory, known as a syndrome decoding problem, and analyzed using cryptanalytic means. Namely, we analyze the time complexity of the information set decoding algorithms, widely believed to be the best algorithms for solving the syndrome decoding problem. By evaluating their complexity, both in the classical and quantum domain, we reason about the hardness of the problem. Finally, we give an example of the scheme based upon the syndrome decoding problem and analyze its security imposed by the hardness of the problem. We examine the tradeoff between signature's security and its size, which is a major challenge to be addressed in the competition.

One world numeration seminar
Mardi 25 janvier 2022, 14 heures 30, Online
Claudio Bonanno (Università di Pisa) Infinite ergodic theory and a tree of rational pairs

The study of the continued fraction expansions of real numbers by ergodic methods is now a classical and well-known part of the theory of dynamical systems. Less is known for the multi-dimensional expansions. I will present an ergodic approach to a two-dimensional continued fraction algorithm introduced by T. Garrity, and show how to get a complete tree of rational pairs by using the Farey sum of fractions. The talk is based on joint work with A. Del Vigna and S. Munday.

Combinatoire énumérative et analytique
Jeudi 27 janvier 2022, 14 heures, Salle 3052 et sur zoom
Elba Garcia-Failde (IMJ-PRG Sorbonne Universite) TBD

Preuves, programmes et systèmes
Jeudi 27 janvier 2022, 10 heures 30, TBA
Titouan Carette (LORIA / Université de Lorraine) Non encore annoncé.

Automates
Vendredi 28 janvier 2022, 14 heures 30, Salle 3052
Nathan Grosshans Undefined

Graph Transformation Theory and Applications
Vendredi 28 janvier 2022, 15 heures, online
William Waites (University of Strathclyde, Scotland, UK) Rule-based Models of Epidemics

Rule-based models, a particular kind of graph rewriting system initially intended for use in molecular biology, are conspicuously useful for understanding epidemics. They enable formulation of complex processes that blends the ease of understanding of “compartmental” models with the expressiveness of individual- or agent-based models. We illustrate this with a story, told in graph rewriting rules, of how the adaptive immune response to a pathogen works (simplified version) and how this response influences the population level dynamics of an epidemic. This model can be calibrated against real-world data and we see how some of the individual heterogeneity that is normally treated phenomenologically in the study of epidemics arises naturally from this account of immune response.

Zoom meeting registration link

YouTube live stream