Institut de Recherche en Informatique Fondamentale (IRIF)


Université Paris Cité

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, 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), six 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.

Conference Highlights 2022

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

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

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

Institut Universitaire de France

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

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

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

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

Accepted paper ICALP 2022

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

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

Algorithmes et complexité
Mardi 28 juin 2022, 11 heures, Salle 3052
Rajat Mittal (IIT Kanpur) Quantum query complexity (what, why and how)

Quantum query model has been one of the main tools in quantum computing for understanding the complexity of problems: both in terms of designing efficient algorithms, and giving lower bounds on the complexity of the problem. In case of lower bounds, the main benefit of query model is the fact that concrete mathematical techniques exist to understand the query complexity. Our main aim in this talk is to look at this computational model and see why this model has gained so much attention in the quantum computing world.

After looking at the background and definitions for the query model, we will look at reasons why quantum query complexity is an important area of study. Not just that it is one of the simplest settings to study the complexity of functions, it naturally arises in many other areas like property testing and communication complexity.

Finally, as mentioned before, there exist many mathematical tools to study quantum query complexity. We will talk about the two main lower bound methods: adversary and polynomial. It will allow us to give a very short proof that Grover search is optimal. For the case of symmetric functions, we will see that simple arguments allow us to characterize not just the query complexity but even its lower bound techniques.

Algorithmes et complexité
Mardi 28 juin 2022, 15 heures, Salle 3052
Manaswi Paraashar (Aarhus University) Quantum weirdness in query-to-communication simulation and the role of symmetry

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function $f : \{0,1\}^n \to \{0,1\}$ and $G \in \{AND_2, XOR_2\}$, the bounded-error quantum communication complexity of the composed function ($f \circ G$) equals $O(Q(f) \log n)$, where $Q(f)$ denotes the bounded-error quantum query complexity of $f$. This is known as the BCW Simulation Theorem. This is in contrast with the classical setting, where it is easy to show that $R^{cc}(f \circ G) \leq 2R(f)$, where $R^{cc}$ and $R$ denote bounded-error communication and query complexity, respectively. We exhibited a total function for which the $\log n$ overhead in the BCW simulation is required.

We also answer several other questions related to quantum query-to-communication simulation: 1. We show that the $\log n$ overhead is not required when $f$ is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). 2. One may ask whether the $\log n$ overhead in the BCW Simulation Theorem can be avoided even when f is transitive, which is a weaker notion of symmetry. We show that the $\log n$ overhead is necessary for some transitive functions, even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication). 3. We also give, among other things, a general recipe to construct functions for which the $\log n$ overhead is required in the BCW Simulation Theorem in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.

This talk is based on two joint works with Sourav Chakraborty, Arkadev Chattopadhyay, Peter Hoyer, Nikhil Mande, and Ronald de Wolf.

Mardi 28 juin 2022, 9 heures 30, Salle 3052
Eigil Fjeldgren Rischel (University of Strathclyde) An invitation to categorical cybernetics

Over the past ~5 years, a number of authors trying to apply methods from category theory to game theory, machine learning, and dynamical systems, have noticed a strong convergence. It seems that very similar categorical structures emerge from the study of all of these things, centering around the notion of /lens/. I'll give a survey of this research program and sketch some recent advances.

Graph Transformation Theory and Applications
Mercredi 29 juin 2022, 19 heures, online
John Baez (Department of Mathematics, University of California, Riverside, USA) ★★★ GReTA Special Event ★★★ Compositional Modeling with Decorated Cospans

Decorated cospans are a general framework for composing open networks and mapping them to dynamical systems. We explain this framework and illustrate it with the example of stock and flow diagrams. These diagrams are widely used in epidemiology to model the dynamics of populations. Although tools already exist for building these diagrams and simulating the systems they describe, we have created a new software package called StockFlow which uses decorated cospans to overcome some limitations of existing software. Our approach cleanly separates the syntax of stock and flow diagrams from the semantics they can be assigned. We have implemented a semantics where stock and flow diagrams are mapped to ordinary differential equations, although others are possible. We illustrate this with code in StockFlow that implements a simplified version of a COVID-19 model used in Canada. This is joint work with Xiaoyan Li, Sophie Libkind, Nathaniel Osgood and Evan Patterson.

Zoom meeting registration link

YouTube live stream

Combinatoire énumérative et analytique
Jeudi 30 juin 2022, 14 heures, Salle 1007
Lucia Rossi (Graz) Limit words for $N$-continued fractions

Given $N\geq 1$ and $x \in [0, 1]\backslash \mathbb{Q}$, an $N$-continued fraction expansion of $x$ is defined analogously as the classical continued fraction, but with the numerators being all equal to $N$. We introduce two infinite words $\omega(x, N )$ and $\hat\omega(x, N )$ on a two letter alphabet, which are related to the $N$-continued fraction expansion of $x$ and are obtained as a limit word of a sequence of substitutions. We call them $N$-continued fraction words. When $N=1$, we are in the classical case and find a Sturmian word. We show that these words are $C$-balanced for some explicit values of $C$, and we compute the factor complexity function of both families of words. We relate this to the more general setting of limit words of non unimodular $S$-adic sequences.

This is joint work with Jörg Thuswaldner and Niels Langeveld.

Analyse et conception de systèmes
Vendredi 1 juillet 2022, 10 heures 30, Salle 3052
Jean-Baptiste Tristan (Boston College) Probabilistic Programming and Molecular Optimization (Zoom link)

The energy of a system of atoms is approximately a function of the position of the nuclei. This function is called the potential energy surface (PES). Knowledge of the PES is fundamental in ab-initio sciences but unfortunately, it cannot be computed in closed form. As a result, an important problem is that of exploring the PES to discover important features, such as local minima.

In this talk, I will introduce an experimental probabilistic programming language designed to facilitate the exploration of PES. In this language, the semantics of a program is a probability distribution over PES. The objective of the compiler is to generate an optimizer that combines solvers from machine learning and quantum chemistry to discover local minima of the PES. While much of this language and compiler is routine, we will see that the principle of conservation of energy brings about genuinely interesting compilation problems.

One world numeration seminar
Mardi 5 juillet 2022, 14 heures 30, Online
Charlene Kalle (Universiteit Leiden) Random Lüroth expansions

Since the introduction of Lüroth expansions by Lüroth in his paper from 1883 many results have appeared on their approximation properties. In 1990 Kalpazidou, Knopfmacher and Knopfmacher introduced alternating Lüroth expansions and studied their properties. A comparison between the two and other comparable number systems was then given by Barrionuevo, Burton, Dajani and Kraaikamp in 1996. In this talk we introduce a family of random dynamical systems that produce many Lüroth type expansions at once. Topics that we consider are periodic expansions, universal expansions, speed of convergence and approximation coefficients. This talk is based on joint work with Marta Maggioni.

Analyse et conception de systèmes
Vendredi 8 juillet 2022, 10 heures 30, Salle 1007
Ada Vienot (IRIF) A reactive operational semantics for a lambda-calculus with time warps

Many computer systems are reactive: they execute in continuous interaction with their environment. From the perspective of functional programming, reactive systems can be modeled and programmed as stream functions. Several lines of research have exploited this point of view. Works based on Nakano’s guarded recursion use type-theoretical modalities to guarantee productivity. Works based on synchronous programming use more specialized methods but guarantee incremental processing of stream fragments. In this paper, we contribute to a recent synthesis between the two approaches by describing how a language with a family of type-theoretical modalities can be given an incremental semantics in the synchronous style. We prove that this semantics coincides with a more usual big-step semantics.

Algorithmes et complexité
Mardi 12 juillet 2022, 10 heures, Salle 3052
Seeun William Umboh (The University of Sydney) Online Weighted Cardinality Joint Replenishment Problem with Delay

We study a generalization of the classic Online Joint Replenishment Problem (JRP) with Delays that we call the Online Weighted Cardinality JRP with Delays. The JRP is an extensively studied inventory management problem wherein requests for different item types arrive at various points in time. A request is served by ordering its corresponding item type. The cost of serving a set of requests depends on the item types ordered. Furthermore, each request incurs a delay penalty while it is left unserved. The objective is to minimise the total service and delay costs. In the Weighted Cardinality JRP, each item type has a positive weight and the cost of ordering is a non-decreasing, concave function of the total weight of the item types ordered. This problem was first considered in the offline setting by Cheung et al.~(2015) but nothing is known in the online setting. Our main result is a deterministic, constant competitive algorithm for this problem.

Algorithmes et complexité
Mardi 12 juillet 2022, 11 heures, Salle 3052
Kheeran Naidu (University of Bristol) Space Optimal Vertex Cover in Dynamic Streams (with an overview of graph streaming)

With the world as connected as ever and data being created at an unprecedented rate, there has been an increasing need for algorithms that efficiently process massive graphs. Graph streaming is one such memory efficient setting where the edges of a graph are presented as a sequence of edges and an algorithm's goal is to store a sublinear number of edges needed to solve a graph problem exactly or approximately. In particular, this talk discusses the insertion-only, dynamic (or insertion-deletion) and sliding window graph streaming models of computation, highlighting the well-studied maximum matching and sister minimum vertex cover problems, and focusing on a recent space optimal (up to constant factors) algorithm for minimum vertex cover in the dynamic graph streaming model.