Institut de Recherche en Informatique Fondamentale (IRIF)


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

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.

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 !

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.

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.

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.

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

Vendredi 18 juin 2021, 14 heures 30,
Charles Paperman Dynamic Membership for regular language

We study the dynamic membership problem for regular languages: fix a language L, read a word w, build in time O(|w|) a data structure indicating if w is in L, and maintain this structure efficiently under substitution edits on w. We consider this problem on the unit cost RAM model with logarithmic world length, where the problem always has a solution in O(log |w| / log log |w|). We show that the problem is in O(log log |w|) for languages in an algebraically-defined class QSG, and that it is in O(1) for another class QLZG. We show that languages not in QSG admit a reduction from the prefix problem for a cyclic group, so that they require \Omega(log n/ log log n) operations in the worst case; and that QSG languages not in QLZG admit a reduction from the prefix problem for the monoid U_1, which we conjecture cannot be maintained in O(1). This yields a conditional trichotomy. We also investigate intermediate cases between O(1) and O(log log n). Our results are shown via the dynamic word problem for monoids and semigroups, for which we also give a classification. We thus solve open problems of the paper of Skovbjerg Frandsen, Miltersen, and Skyum on the dynamic word problem, and additionally cover regular languages.

Algorithmes et complexité
Mardi 22 juin 2021, 11 heures, Salle 3052 + Zoom
Subhasree Patro (CWI) Quantum Fine-Grained Complexity

One of the major challenges in the field of complexity theory is the inability to prove unconditional time lower bounds, including for practical problems within the complexity class P. One way around this is the study of fine-grained complexity where we use special reductions to prove time lower bounds for many diverse problems in P based on the conjectured hardness of some key problems. For example, computing the edit distance between two strings, a problem that has a practical interest in the comparing of DNA strings, has an algorithm that takes O(n^2) time. Using a fine-grained reduction it can be shown that faster algorithms for edit distance also imply a faster algorithm for the Boolean Satisfiability (SAT) problem (that is believed to not exist) - strong evidence that it will be very hard to solve the edit distance problem faster. Other than SAT, 3SUM, and APSP are other such key problems that are very suitable to use as a basis for such reductions, since they are natural to describe and well-studied.

The situation in the quantum regime is no better; almost all known lower bounds for quantum algorithms are defined in terms of query complexity, which doesn’t help much for problems for which the best-known algorithms take superlinear time. Therefore, employing fine-grained reductions in the quantum setting seems a natural way forward. However, translating the classical fine-grained reductions directly into the quantum regime is not always possible for various reasons. In this talk, I will present some recent results in which we circumvent these challenges and prove quantum time lower bounds for some problems in BQP conditioned on the conjectured quantum hardness of SAT (and its variants) and the 3SUM problem.

One world numeration seminar
Mardi 22 juin 2021, 14 heures 30, Online
Lingmin Liao (Université Paris-Est Créteil Val de Marne) Simultaneous Diophantine approximation of the orbits of the dynamical systems x2 and x3

We study the sets of points whose orbits of the dynamical systems x2 and x3 simultaneously approach to a given point, with a given speed. A zero-one law for the Lebesgue measure of such sets is established. The Hausdorff dimensions are also determined for some special speeds. One dimensional formula among them is established under the abc conjecture. At the same time, we also study the Diophantine approximation of the orbits of a diagonal matrix transformation of a torus, for which the properties of the (negative) beta transformations are involved. This is a joint work with Bing Li, Sanju Velani and Evgeniy Zorin.

Preuves, programmes et systèmes
Jeudi 24 juin 2021, 17 heures, Online at link (any password works)
Michael Shulman (University of San Diego) Non encore annoncé.

Vendredi 25 juin 2021, 14 heures 30,
Amina Doumane Tree-to-tree functions

We study tree-to-tree transformations that can be defined in first-order logic or monadic second-order logic. We prove a decomposition theorem, which shows that every transformation can be obtained from prime transformations, such as tree-to-tree homomorphisms or pre-order traversal, by using combinators such as function composition.