Institut de Recherche en Informatique Fondamentale (IRIF)

CNRS

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.

One-year visitor - Lauren K. Williams

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

Accepted paper ITCS 2023 - Sophie Laplante

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

Prix informatique Lovelace-Babbage 2023

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

The EQSI is launched

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

Nomination IUF - Olivier Carton

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

Accepted papers SODA 2023 - Adrian Vladu

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

Accepted papers SODA 2023 - Guillaume Chapuy

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

Synthèse nationale des Mathématiques

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


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

Combinatoire énumérative et analytique
Jeudi 8 décembre 2022, 14 heures, Salle 3052 et zoom
Amanda Burcroff (Harvard) Dyck Path Expansion Formulas for Rank 2 Cluster Algebras

The theory of cluster algebras, introduced twenty years ago by Fomin and Zelevinsky, gives us a combinatorial framework for understanding the previously opaque nature of certain algebras. Each cluster algebra is generated by its cluster variables, which are defined recursively via the process of mutation. In the rank two case, several explicit formulas have been given for the cluster variables in terms of combinatorial, representation theoretic, and tropical objects. We will focus on two such formulas. The first, given by Lee-Schiffler, sums over collections of colored Dyck subpaths, and the second, given by Lee-Li-Zelevinsky, sums over compatible pairs in Dyck paths. We will discuss a correspondence between these two sets of objects, as well as a simplification and quantum generalization of the Lee-Schiffler expansion formula.

Preuves, programmes et systèmes
Jeudi 8 décembre 2022, 10 heures 30, Salle 3052 & online (Zoom link)
Beniamino Accattoli (INRIA Saclay, PARTOUT Project-Team) Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic.

In this talk, I will start by discussing the lack of a reasonable time cost model for linear logic. Then, inspired by recent advances in the sister field of lambda calculus, I will introduce a new term-based presentation of cut elimination for IMELL admitting a reasonable strategy (that is, a strategy of which the number of step is a reasonable time cost model). The focus will be on the principles behind the new presentation of cut elimination.

Séminaire des doctorants
Jeudi 8 décembre 2022, 16 heures, 3052 and Zoom link
Srinidhi N Domain specific language for Testing consensus implementations

I will introduce some consensus protocols and give an overview of some of the implementations. Following that, I will introduce what are the existing approaches to testing the implementations and then explain our approach which is akin to unit testing.

No prior knowledge of distributed systems/algorithms is required.

Catégories supérieures, polygraphes et homotopie
Vendredi 9 décembre 2022, 14 heures, Salle 1007
Manuel Araujo (Cambridge University) String diagrams for n-sesquicategories

I will talk about work in progress on a theory of semistrict n-categories, where composition is strictly associative and unital, but the interchange laws hold up to coherent equivalence. The idea is to define a semistrict n-category as something which admits composites for labelled string diagrams. The first step is to develop a theory of n-sesquicategories. These encode only the compositional structure of string diagrams, without the interchange laws. I will explain how to define these as algebras over a globular operad whose operations are simple string diagrams, and how to prove that the associated category of computads is a presheaf category. The second step, which is still work in progress, is to add operations implementing the interchange laws up to coherent equivalence, obtaining the desired notion of semistrict n-category. In dimension 3, this recovers the notion of Gray 3-category.

https://arxiv.org/abs/2202.09293 ; https://arxiv.org/abs/2210.07704

Automates
Vendredi 9 décembre 2022, 14 heures, Salle 3052
Sarah Winter A Regular and Complete Notion of Delay for Streaming String Transducers

The notion of delay between finite transducers is a core element of numerous fundamental results of transducer theory. The goal of this work is to provide a similar notion for more complex abstract machines: we introduce a new notion of delay tailored to measure the similarity between streaming string transducers (SST).

We show that our notion is regular: we design a finite automaton that can check whether the delay between any two SSTs executions is smaller than some given bound. As a consequence, our notion enjoys good decidability properties: in particular, while equivalence between non-deterministic SSTs is undecidable, we show that equivalence up to fixed delay is decidable. Moreover, we show that our notion has good completeness properties: we prove that two SSTs are equivalent if and only if they are equivalent up to some (computable) bounded delay.

Together with the regularity of our delay notion, it provides an alternative proof that SSTs equivalence is decidable. Finally, the definition of our delay notion is machine-independent, as it only depends on the origin semantics of SSTs. As a corollary, the completeness result also holds for equivalent machine models such as deterministic two-way transducers, or MSO transducers.

This is joint work with Emmanuel Filiot, Ismaël Jecker, and Christof Löding.

Vérification
Lundi 12 décembre 2022, 11 heures, 1007 and Zoom link
Salim Chouai (Mohammed VI University) Synthesis of Accuracy Specification under Differential Privacy

Differential privacy (DP) is a mathematical framework for developing statistical computations with provable guarantees of privacy and accu- racy. In contrast to the privacy component of DP, which has a clear mathematical and intuitive meaning, the accuracy component of differential privacy does not have a generally accepted definition; accuracy claims of differential privacy algorithms vary from algorithm to algorithm and are not instantiations of a general definition. We have identified common themes in existing ad hoc definitions and introduced an alternative notion of accuracy parametrized by a reference specification φ. We say that a DP algorithm is (μ, β)−accurate w.r.t to φ iff φ is ’almost true’ with tolerance μ and a high probability 1 − β. We proposed a synthesis method, that takes as an input the program specification φ and produces a probabilistic accuracy statement. Our approach applies to programs that are made DP by introducing a random noise to their input. The approach is systematic and is reduced only on logical reasoning. It uses axiomatic properties of probability distributions combined with FO deductive techniques in order to derive an probabilistic accuracy specification about the DP program from the specification of the original program. In order to make tighter accuracy statements, we proposed an extension to our approach that takes into account assumptions about the input values and reason about accuracy without compromising the privacy.

One world numeration seminar
Mardi 13 décembre 2022, 14 heures, Online
Hiroki Takahasi (Keio University) Distribution of cycles for one-dimensional random dynamical systems

We consider an independently identically distributed random dynamical system generated by finitely many, non-uniformly expanding Markov interval maps with a finite number of branches. Assuming a topologically mixing condition and the uniqueness of equilibrium state for the associated skew product map, we establish a samplewise (quenched) almost-sure level-2 weighted equidistribution of “random cycles”, with respect to a natural stationary measure as the periods of the cycles tend to infinity. This result implies an analogue of Bowen's theorem on periodic orbits of topologically mixing Axiom A diffeomorphisms.

This talk is based on the preprint arXiv:2108.05522. If time permits, I will mention some future perspectives in this project.

Algorithmes et complexité
Mercredi 14 décembre 2022, 11 heures, Salle 3052
Fabien Dufoulon (University of Houston) Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity

Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best-known (randomized) MIS algorithms have O(log n) round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best-known lower bound is Ω(√(log(n)/log(log n))) [Kuhn, Moscibroda, and Wattenhofer, JACM 2016]. Breaking past the O(log n) bound or showing stronger lower bounds have been longstanding open problems.

Energy is a premium resource in battery-powered wireless and sensor networks, and the bulk of it is used by nodes when they are awake, i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping, it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake, also called the awake complexity. An intriguing question is whether one can design a distributed MIS algorithm that is significantly more energy-efficient (having very small awake complexity) compared to existing algorithms.

Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of O(log n) and also bypassing its fundamental Ω(√(log(n)/log(log n))) round complexity lower bound (almost) exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in O(log log n) awake complexity with high probability. Since a node spends significant energy only in its awake rounds, our result shows that MIS can be computed in a highly energy-efficient way compared to the existing MIS algorithms.

Algorithmes et complexité
Mercredi 14 décembre 2022, 14 heures, Salle 3052
Hang Zhou (École Polytechnique) Unsplittable Euclidean Capacitated Vehicle Routing

In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1.

Our main result is a polynomial-time $(2+\epsilon)$-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].

This is joint work with Claire Mathieu and Fabrizio Grandoni.

Théorie des types et réalisabilité
Mercredi 14 décembre 2022, 14 heures, Salle 1007
Rémy Cerda (Institut de Mathématiques de Marseille, Université Aix-Marseille) Non encore annoncé.